70分 求指导

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

Docu @ 2017-08-10 13:26:16

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,ans,v,p,q;
int g[60][5],a[60][5];
int f[32000],b[60];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>v>>p>>q;
        if(q==0)
        {
            ans++;
            g[ans][1]=v*p;
            a[ans][1]=v;
            b[i]=ans;
        }
        else{
            if(g[b[q]][2]==0)
            {
                g[b[q]][2]=v*p+g[b[q]][1];
                a[b[q]][2]=v+a[b[q]][1];
            }
            else{
                g[b[q]][3]=v*p+g[b[q]][1];
                a[b[q]][3]=v+a[b[q]][1];
            }
        }
    }
    for(int i=1;i<=ans;i++) 
    if(g[i][2]!=0||g[i][3]!=0)
       g[i][4]=g[i][2]+g[i][3]-g[i][1],a[i][4]=a[i][2]+a[i][3]-a[i][1];
    for(int k=1;k<=ans;k++)
       for(int i=n;i>=0;i--)
          for(int j=1;j<5;j++)
          {
              if(i>=a[k][j])
                f[i]=max(f[i],f[i-a[k][j]]+g[k][j]);
          }
    cout<<f[n];
    return 0;      
}

by ouuan @ 2017-08-30 20:35:27

我之前也是70,记忆化搜索就过了


|