80fen,求救大牛们!!!!

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

少帅_zjm @ 2017-10-02 13:42:40

#include <bits/stdc++.h>
using namespace std;
struct node 
{
    int x,y;
    int sum;
}f;
vector<node> qq[100];
int main()
{
    freopen("in.txt","r",stdin);
    int V,n;
    cin>>V>>n;
//    cout<<V<<n<<endl;
    int a[100][3]={0};
    int dp[40000]={0};
    for(int i=1;i<=n;i++)
    {
        int k,m,p;
        cin>>k>>m>>p;
//        cout<<k<<m<<p<<endl;
        if(p>0)
        {
            f.x=k;f.y=m;
            f.sum=k*m;
            qq[p].push_back(f);
        //    cout<<"b"<<qq[p][0].sum<<endl;
        }
        //差一个技术器。。。
        else
        {
            a[i][1]=k;a[i][2]=m;
            a[i][3]=a[i][1]*a[i][2];
        //    cout<<a[i][1]<<a[i][2]<<a[i][3]<<endl;
         } 

}//输入之前的预处理。。。

    for(int i=1;i<=n;i++)
    if(a[i][1]!=0)
//    cout<<a[i][3];
    for(int j=V;j>=a[i][1];j--)
    {
    dp[j]=max(dp[j],dp[j-a[i][1]]+a[i][3]);
    if(qq[i].size()==1&&j>=a[i][1]+qq[i][0].x)
    dp[j]=max(dp[j-a[i][1]]+a[i][3],dp[j-qq[i][0].x-a[i][1]]+qq[i][0].sum+a[i][3]);
    if(qq[i].size()==2&&j>=a[i][1]+qq[i][1].x)
       dp[j]=max(dp[j-a[i][1]]+a[i][3],dp[j-qq[i][1].x-a[i][1]]+qq[i][1].sum+a[i][3]);
       if(qq[i].size()==2&&j>=a[i][1]+qq[i][1].x+qq[i][0].x)
       dp[j]=max(dp[j-a[i][1]]+a[i][3],dp[j-qq[i][0].x-qq[i][1].x-a[i][1]]+qq[i][0].sum+qq[i][1].sum+a[i][3]);
   //bug空间容量大小 
   }
//    int ma=-1;
  //   for(int i=1;i<=V;i++)
    // ma=max(ma,dp[i]);
//    cout<<dp[i]<<endl;
    cout<<dp[V];
    return 0;
}

|