首页 > 代码库 > TYVJ1057

TYVJ1057

2024-07-19 06:54:54   211人阅读

这题我真的不想说什么了，真尼玛恶心，整整一个晚上，就让一个下标从0从1开始给整这了
这题本身确实不难，就是麻烦，交了8次，错了8次，本来以为是状态转移的时候出了问题，一直在那找，改了改又改，从对改到错，又从错改到更错，最后没办法又找的别人的代码。。算了，啥也不多说了。。
就是个01背包

DP时，对于附件直接跳过，主件分几次情况判断下就好，每个主件的决策太多了。。。
直接看代码吧。。

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6  7 const int maxv = 32005; 8 const int maxn = 70; 9 10 struct node11 {12     int v,w,q,cnt;13     int s[2];14 }a[maxn];15 int dp[maxv];16 int main()17 {18     //freopen("in.txt","r",stdin);19     int n,m;20     cin>>m>>n;21     memset(a,0,sizeof(a));22     for(int i = 1;i<=n;++i)23     {24         int x,y,z;25         scanf("%d%d%d",&x,&y,&z);26         if(z)27         {28 29             a[i].w = x;30             a[i].v = x*y;31             a[i].q = z;32             a[z].s[a[z].cnt] = i;33             a[z].cnt++;34         }35         else36         {37             a[i].w = x;38             a[i].v = x*y;39             a[i].q = 0;40         }41     }42     memset(dp,0,sizeof(dp));43     for(int i = 1;i<=n;++i)44     {45         if(a[i].q)continue;46         for(int j = m;j>=0;--j)47             if(j>=a[i].w)48             {49                 dp[j] = max(dp[j],dp[j-a[i].w]+a[i].v);50                 if(a[i].cnt>=1)51                 {52                     int x = a[i].s[0];53                     if(j>=a[i].w+a[x].w)dp[j]=max(dp[j],dp[j-a[i].w-a[x].w]+a[i].v+a[x].v);54                     if(a[i].cnt>=2)55                     {56                         int y = a[i].s[1];57                         if(j>=a[i].w+a[y].w)dp[j]=max(dp[j],dp[j-a[i].w-a[y].w]+a[i].v+a[y].v);58                         if(j>=a[i].w+a[x].w+a[y].w)59                             dp[j]=max(dp[j],dp[j-a[i].w-a[x].w-a[y].w]+a[i].v+a[x].v+a[y].v);60                     }61                 }62 63             }64     }65     printf("%d\n",dp[m]);66 67     return 0;68 }

 

TYVJ1057


联系
我们