0分求助qwq

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

monkey123456 @ 2022-08-21 15:31:48

#include<stdio.h>
int dp[35005];
int max(int a,int b)、
{
    if(a<b) return b;
    return a;
} 
int flag[35005];
int main()
{
    int T,num,n[1005],v[1005];//钱   n个数   钱  重要
    int q[1005];//配件 
    scanf("%d%d",&T,&num);
    for(int i=1;i<=num;i++) scanf("%d%d%d",&n[i],&v[i],&q[i]);
    for(int i=1;i<=num;i++)
    {
        for(int j=T;j>=0;j--)
        {
            if(q[i]==0)               // 主件 
            {
                if(j>=n[i]) dp[j]=max(dp[j],dp[j-n[i]]+n[i]*v[i]);
                flag[i]=114514;
            }
            else                      // 配件 
            {
                if(flag[q[i]]==114514)// 买过主件 
                {
                    if(j>=n[i]) dp[j]=max(dp[j],dp[j-n[i]]+n[i]*v[i]);
                }
                else if( flag[q[i]]!=114514 )         // 没买主件 
                {
                    if(j>=(n[q[i]]+n[i]))
                    {
                        dp[j]=max(dp[j],dp[j-n[q[i]]-n[i]]+n[i]*v[i]+n[q[i]]*v[q[i]]);
                        flag[q[i]]=114514;
                    } 
                }
            }
        }
    }
    printf("%d",dp[T]);
    return 0;
}

by monkey123456 @ 2022-09-06 12:41:46

@Programmerdcr 你还是不是人啦!


by Programmerdcr @ 2022-09-12 13:43:36

@monkey123456 你是不是香精鉴于,菊爆了


|