死活不过两个点求指正

P1064 [NOIP2006 提高组] 金明的预算方案

ygsldr @ 2017-07-10 09:17:24

如题

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
#include <cstring>
#include <map>
#include <cstdlib>
#include <queue>
using namespace std;
int max(int a, int b);
int min(int a, int b);
int read();
void write(int x);
struct obj
{
    int toward1, toward2;//指向两个附件
    int cost, imp, mostcost;//单件消耗,单件重要程度,连带附件消耗
    bool dododo;//是否为附件
}a[60];
int dp[40000];
int main()
{
    int m(read()), n(read()), tmp1, tmp2, tmp3;
    for (int i(1); i <= n; ++i)
    {
        a[i].toward1 = 0;
        a[i].toward2 = 0;
        a[i].mostcost = 0;
        a[i].dododo = true;
    }//初始化
    for (int i(1); i <= n; ++i)
    {
        tmp1 = read();//价格
        tmp2 = read();//重要度
        tmp3 = read();//附件
        tmp2 *= tmp1;//相乘为val
        a[i].cost = tmp1;//记录消耗的钱
        a[i].imp = tmp2;//记录val
        if (tmp3 == 0)
        {
            a[i].mostcost += a[i].cost;//如果为主件,累加最大值
            continue;
        }
        else
        {
            a[tmp3].mostcost += a[i].cost;//如果为附件,将消耗累加到他的主件上
            a[i].dododo = false;//该件不能单独取
            if (a[tmp3].toward1 == 0)a[tmp3].toward1 = i;
            else a[tmp3].toward2 = i;//记录此附件的位置
        }
    }
    for (int i(1); i <= n; ++i)
    {
        if (a[i].dododo == false)continue;//跳过附件
        for (int j(m); j >= a[i].mostcost; --j)
        {
            dp[j] = max(dp[j], dp[j - a[i].cost] + a[i].imp);//只取A
            if (a[i].toward1)
            {
                dp[j] = max(dp[j], dp[j - a[i].cost - a[a[i].toward1].cost] + a[i].imp + a[a[i].toward1].imp);//取A,B
            }
            if (a[i].toward2)
            {
                dp[j] = max(dp[j], dp[j - a[i].cost - a[a[i].toward2].cost] + a[i].imp + a[a[i].toward2].imp);//取A,C;A,B,C
                dp[j] = max(dp[j], dp[j - a[i].cost - a[a[i].toward1].cost - a[a[i].toward2].cost] + a[i].imp + a[a[i].toward1].imp + a[a[i].toward2].imp);
            }
        }
    }
    write(dp[m]);//输出
    return 0;
}
inline int max(int a, int b)
{
    return a > b ? a : b;
}
inline int min(int a, int b)
{
    return a < b ? a : b;
}
inline int read()
{
    int x(0), f(1);
    char ch = getchar();
    while (ch > '9' || ch < '0')
    {
        if (ch == '-')f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void write(int x)
{
    if (x == 0)
    {
        putchar('0');
        return;
    }
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    char ch[20];
    int num(0);
    while (x > 0)
    {
        ch[num] = x % 10 + '0';
        x /= 10;
        ++num;
    }
    for (int i(num - 1); i >= 0; --i)putchar(ch[i]);
    return;
}

|