谁帮帮我啊

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

我是星星 @ 2017-08-30 15:06:13

#include<iostream>
using namespace std;
int v[100],f[100][32001],k,r[100],p[100],o[100],n,m;
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>p[i]>>o[i];          //分别读入为物品i的价值,重要度,主件序号
    }
    k=n;
    for(int i=1;i<=n;i++)
      if(o[i])
        if(r[o[i]]==0)
        {
            v[++k]=v[o[i]]+v[i];p[k]=p[o[i]]+p[i];r[o[i]]=i;       //r[i]表示物件i的第一个附件的序号 
            v[i]=0;p[i]=0;                         //o[i]表示物件i的主件的序号 
        }
        else 
        {
            v[++k]=v[o[i]]+v[i]+v[r[o[i]]];p[k]=p[o[i]]+p[i]+p[r[o[i]]];
            v[++k]=v[o[i]]+v[i];p[k]=p[o[i]]+p[i];
            v[i]=0;p[i]=0;
        }
        for(int i=1;i<=k;i++)
          for(int j=m;j>=1;j--)
             if(v[i]<=j)
                f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+v[i]*p[i]); 
                  else f[i][j]=f[i-1][j];
    cout<<f[k][m];
    return 0;
}
求帮忙

by Out_Land @ 2017-08-30 16:42:26

在取时顺便计算值,选最优的


by Out_Land @ 2017-08-30 16:45:38

然后,状态转移方程.写的.可能.有点.多,不过很好写的~~~


by angleの奏 @ 2017-08-30 16:46:02

@2556937429lq 样例能过吗


by angleの奏 @ 2017-08-30 16:46:35

@2556937429lq 似乎发现了错误,但改了以后过不了样例


by angleの奏 @ 2017-08-30 16:47:10

@2556937429lq 还有你的r是什么


by Out_Land @ 2017-08-30 16:47:46

dalao出现!!


by Out_Land @ 2017-08-30 16:49:02

我一个小小蒟蒻还是跑吧(活捉大佬一位,逃)


by 我是星星 @ 2017-08-30 16:52:21

我给注释了r[i]表示物件i的第一个附件的序号


by angleの奏 @ 2017-08-30 16:53:18


by 我是星星 @ 2017-08-30 16:55:12

还能改吗


上一页 | 下一页