60分,哪里错了?

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

456laji @ 2020-09-10 23:52:53

码风不好,请大佬们见谅。

#include<bits/stdc++.h>
using namespace std;
const int N=3200+100;
struct node
{
    int price;
    int degree;
}w[N];
int n,m,dp[N],num[N][N],vis[N];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int p=0;
        scanf("%d%d%d",&w[i].price,&w[i].degree,&p);
        if(p!=i&&p!=0)
            vis[i]=1,num[p][0]++,num[p][num[p][0]]=i;
    }

    //for(int i=1;i<=m;i++)
    //  printf("%d %d \n",num[i][1],num[i][2]);

    for(int i=1;i<=m;i++)
    {
        if(vis[i]) continue;
        for(int j=n;j>=w[i].price;j--)
        {
            dp[j]=max(dp[j],dp[j-w[i].price]+w[i].price*w[i].degree);

            if(num[i][0]==1)
            {
                int a=num[i][1];
                if(j>=w[i].price+w[a].price)
                    dp[j]=max(dp[j],dp[j-w[i].price-w[a].price]+(w[i].degree*w[i].price)+(w[a].degree*w[a].price));
            }
            if(num[i][0]==2)
            {
                int a=num[i][1],b=num[i][2];
                if(j>=w[i].price+w[a].price)
                    dp[j]=max(dp[j],dp[j-w[i].price-w[a].price]+(w[i].degree*w[i].price)+(w[a].degree*w[a].price));
                if(j>=w[i].price+w[b].price)
                    dp[j]=max(dp[j],dp[j-w[i].price-w[b].price]+(w[i].degree*w[i].price)+(w[b].degree*w[b].price));
                if(j>=w[i].price+w[a].price+w[b].price)
                    dp[j]=max(dp[j],dp[j-w[i].price-w[a].price-w[b].price]+(w[i].degree*w[i].price)+(w[a].degree*w[a].price)+(w[b].degree*w[b].price));
            }
        }
    }
    printf("%d\n",dp[n]);
    return 0;
}

by Flora_Wisker @ 2020-10-03 09:04:04

不知道呢,好像没错


|