为什么只有60分

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

huangjingling @ 2020-02-06 18:25:02

#include<stdio.h>
int max(int a,int b){return (a>b)?a:b;}
int main()
{
    int dp[32010]={0};
    int v[65][3]={0},w[65][3]={0};
    int n,m,count=0;
    scanf("%d %d",&n,&m);
    for(int i=0,j=0,k=1;j<m;j++)
    {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        if(z==0){i++;v[i][0]=x;w[i][0]=y;count++;}
        else if(z!=0){k=1;if(w[z][k]!=0)k=2;v[z][k]=x;w[z][k]=y;}

    }
    for(int i=1;i<=count;i++)
        for(int j=n;j>=0;j--)
    {
        if(j>=v[i][0])dp[j]=max(dp[j],dp[j-v[i][0]]+w[i][0]*v[i][0]);
        if((j>=(v[i][0]+v[i][1]))&&w[i][1]!=0)dp[j]=max(dp[j],dp[j-v[i][0]-v[i][1]]+v[i][0]*w[i][0]+v[i][1]*w[i][1]);
        if((j>=(v[i][0]+v[i][2]))&&w[i][2]!=0)dp[j]=max(dp[j],dp[j-v[i][0]-v[i][2]]+v[i][0]*w[i][0]+v[i][2]*w[i][2]);
        if((j>=(v[i][0]+v[i][1]+v[i][2]))&&w[i][1]!=0&&w[i][2]!=0)dp[j]=max(dp[j],dp[j-v[i][0]-v[i][2]-v[i][1]]+v[i][0]*w[i][0]+v[i][1]*w[i][1]+v[i][2]*w[i][2]);
     //printf("dp[%d]=%d\n",j,dp[j]);
    }
    printf("%d",dp[n]);
}

by TonyWu @ 2020-02-18 20:34:22

@huangjingling 这。。。码风我不太习惯。能不能解释一下。


by TonyWu @ 2020-02-18 20:36:04

@huangjingling 我第一次60是因为没有把给的q转换为真正的第q行。

Input

2000 10
500 1 0
400 4 0
300 5 1
400 5 1
200 5 0
500 4 5
400 4 0
320 2 0
410 3 0
400 3 5

Output

7430

by huangjingling @ 2020-02-21 16:05:07

@TonyWu 对,就是这个问题,读题不清


|