大佬进来看,为什么70分,感觉跟题解差不多了

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

chengrundong @ 2018-03-30 11:02:55

include<iostream>

using namespace std; int main() { int i,j,a,b,c,v[61][3],p[61][3],dp[61][1000],n,m; int map[61]={0}; int num=0; cin>>n>>m; n=n/10; for(i=1;i<=m;i++) { cin>>a>>b>>c; if(c==0) { num++; v[num][0]=a/10; p[num][0]=b; map[i]=num; } c=map[c]; if(v[c][1]==0) { v[c][1]=a/10; p[c][1]=b; } else { v[c][2]=a/10; p[c][2]=b; } } for(i=1;i<=num;i++)

{dp[i][0]=0;
    for(j=n;j>=0;j--)
    {

        dp[i][j]=dp[i-1][j];
        if(j>=v[i][0])
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i][0]]+v[i][0]*p[i][0]);
        if(j>=v[i][0]+v[i][1])
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i][0]-v[i][1]]+v[i][0]*p[i][0]+v[i][1]*p[i][1]);
        if(j>=v[i][0]+v[i][2])
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i][0]-v[i][2]]+v[i][2]*p[i][2]+v[i][0]*p[i][0]);
        if(j>=v[i][0]+v[i][1]+v[i][2])
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i][0]-v[i][2]-v[i][1]]+v[i][0]*p[i][0]+v[i][1]*p[i][1]+v[i][2]*p[i][2]);
    }
}
cout<<dp[num][n]*10;
return 0;

}


by chengrundong @ 2018-03-30 11:06:32

include<iostream>

using namespace std;```c


int main()
{
    int i,j,a,b,c,v[61][3],p[61][3],dp[61][8000],n,m;
int map[61]={0};
int num=0;
    cin>>n>>m;
    n=n/10;
    for(i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        if(c==0)
        {
            num++;
            v[num][0]=a/10;
            p[num][0]=b;
            map[i]=num;
        }
        c=map[c];
        if(v[c][1]==0)
        {
        v[c][1]=a/10;
        p[c][1]=b;
        }
        else
        {
        v[c][2]=a/10;
        p[c][2]=b;
        }
    }
    for(i=1;i<=num;i++)

    {dp[i][0]=0;
        for(j=n;j>=0;j--)
        {

            dp[i][j]=dp[i-1][j];
            if(j>=v[i][0])
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i][0]]+v[i][0]*p[i][0]);
            if(j>=v[i][0]+v[i][1])
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i][0]-v[i][1]]+v[i][0]*p[i][0]+v[i][1]*p[i][1]);
            if(j>=v[i][0]+v[i][2])
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i][0]-v[i][2]]+v[i][2]*p[i][2]+v[i][0]*p[i][0]);
            if(j>=v[i][0]+v[i][1]+v[i][2])
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i][0]-v[i][2]-v[i][1]]+v[i][0]*p[i][0]+v[i][1]*p[i][1]+v[i][2]*p[i][2]);
        }
    }
    cout<<dp[num][n]*10;
    return 0;
}

|