70分 卡了好久了 求大牛看看。。

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

效实邹晖 @ 2019-09-25 21:49:30

#include <bits/stdc++.h>
using namespace std;

int n,m;
int v[80][3],val[80][3],f[32115];
void readin()
{
    cin>>n>>m;
    int a,b,c;
    for (int i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        if (c==0)
        {
            v[i][0]=a;
            val[i][0]=a*b;
        }
        else
        {
            if (v[c][1]==0)
            {
                v[c][1]=a;
                val[c][1]=a*b;
            }
            else
            {
                v[c][2]=a;
                val[c][2]=a*b;
            }
        }
    }
}
void work()
{
    for (int i=1;i<=m;i++)
    {
        if (!v[i][0]) continue;
        for (int j=n;j>=1;j--)
        {
            if (v[i][2])
            {
                if (j-v[i][0]-v[i][1]-v[i][2]>=0)
                    f[j]=max(f[j],f[j-v[i][0]-v[i][1]-v[i][2]]+val[i][2]+val[i][1]+val[i][0]);
                else if (j-v[i][0]-v[i][1]>=0)
                    f[j]=max(f[j],f[j-v[i][0]-v[i][1]]+val[i][1]+val[i][0]);
                else if (j-v[i][0]-v[i][2]>=0)
                    f[j]=max(f[j],f[j-v[i][0]-v[i][2]]+val[i][2]+val[i][0]);
                else if (j>=v[i][0])
                    f[j]=max(f[j],f[j-v[i][0]]+val[i][0]);
            }
            else if (v[i][1])
            {
                if (j-v[i][0]-v[i][1]>=0)
                    f[j]=max(f[j],f[j-v[i][0]-v[i][1]]+val[i][1]+val[i][0]);
                else if (j>=v[i][0])
                    f[j]=max(f[j],f[j-v[i][0]]+val[i][0]);
            }
            else
            {
                if (j>=v[i][0])
                    f[j]=max(f[j],f[j-v[i][0]]+val[i][0]);
            }
        }
    }
}

int main()
{
    readin();
    //cout<<endl;
    //  for (int i=1;i<=m;i++)
    // {
    //    cout<<v[i][0]<<" "<<v[i][1]<<" "<<v[i][2]<<endl;
    //    cout<<val[i][0]<<" "<<val[i][1]<<" "<<val[i][2]<<endl<<endl;
    //}
    work();
    cout<<f[n];
    return 0;
}

|