谁帮帮我啊

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:31:39

你的状态转移方程是对的吗??@2556937429lq


by 我是星星 @ 2017-08-30 16:32:59

对,但是我没有分组


by 我是星星 @ 2017-08-30 16:33:30

我想问我这种思路还有救吗


by Out_Land @ 2017-08-30 16:33:55

@2556937429lq 分啥组??


by 我是星星 @ 2017-08-30 16:36:26

就是我用的捆绑思路,吧主件和附件捆绑在一起,有几个策略,但是每组的策略只能选一个,

我的会重复选择,所以错了


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

@2556937429lq 哦哦


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

其实此题可用枚举,枚举每一种情况。


by 我是星星 @ 2017-08-30 16:38:37

嗯嗯


by 我是星星 @ 2017-08-30 16:39:11

你详细说一下


by Out_Land @ 2017-08-30 16:41:01

1:主件和附件全取

2:取主件和附件一

3:取主件和附件二

4:都不取

5:只取主件

~。~


| 下一页