60分。。。WA四个,,求大佬

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

Refun @ 2017-05-21 07:16:36

#include<iostream>
#include<cstring>
using namespace std;
void crf(int v,int sum,int x);
long long n,m,smax,w[62],c[62],p[62],f[61][32001],fj[62][3][3],num[61];
bool pd[62];
int main()
{
    int i,j,s;
    cin>>n>>m;
    s=0;
    int x,y,z;
    for (i=1;i<=m;++i)
    {
        cin>>x>>y>>z;
        y=y*x;
        if (z==0)
        {
            ++s;
            w[s]=x;
            c[s]=y;
        }
        else 
        {
            ++num[z];            
            fj[z][num[z]][1]=x;
            fj[z][num[z]][2]=y;
        }
    }
    for (i=1;i<=s;++i)
    {
        for (j=n;j>=1;--j)
            if (j-w[i]>=0)    
            {
                f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);
                if (j-w[i]-fj[i][1][1]>=0) f[i][j]=max(f[i][j],f[i-1][j-w[i]-fj[i][1][1]]+c[i]+fj[i][1][2]);
                if (j-w[i]-fj[i][2][1]>=0) f[i][j]=max(f[i][j],f[i-1][j-w[i]-fj[i][2][1]]+c[i]+fj[i][2][2]);
                if (j-w[i]-fj[i][2][1]-fj[i][1][1]>=0) f[i][j]=max(f[i][j],f[i-1][j-w[i]-fj[i][1][1]-fj[i][2][1]]+c[i]+fj[i][1][2]+fj[i][2][2]);                                           
            }
            else
                f[i][j]=f[i-1][j];
    }
    cout<<f[s][n];
}

|