首页 > 代码库 > hdu 1712 ACboy needs your help

hdu 1712 ACboy needs your help

2024-10-31 22:56:39   211人阅读

暑假训练第一天有一道CF舞台的题，知道是dp，但是不知道怎么做，听学长讲完以后，最后使用分组背包处理的。（CF至今未补）

分组背包的例题就是hdu 1712

我看了背包九讲的分组背包思路以后，自己写了一下二维的dp数组，一直没有找到哪里转化错误了，一直到看到了另外一位大牛的代码，才知道

 dp[i][j]=max(dp[i][j],dp[i-1][j]);

这一条语句没加，导致上下转移的有问题

使用滚动数组的代码非常多，这里贴出二位的dp数组代码

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int n,m;
 9     while(~scanf("%d %d",&n,&m))
10     {
11         if(n==0&&m==0)
12             break;
13         int a[n+5][m+5];
14         for(int i=1;i<=n;i++)
15             for(int j=1;j<=m;j++)
16                 scanf("%d",&a[i][j]);
17         int  dp[n+5][m+5];
18         memset(dp,0,sizeof(dp));
19         for(int i=1;i<=n;i++){
20             for(int j=m;j>=0;j--){
21                 for(int k=1;k<=j;k++){
22                     dp[i][j]=max(dp[i][j],dp[i-1][j]);
23                     dp[i][j]=max(dp[i][j],dp[i-1][j-k]+a[i][k]);
24 //                    printf("i=%d j=%d k=%d dp[%d] = %d\n",i,j,k,j,dp[j]);
25                 }
26             }
27         }
28 //        for(int i=1;i<=n;i++){
29 //            for(int j=1;j<=m;j++)
30 //                printf("%d ",dp[i][j]);
31 //            printf("\n");
32 //        }
33         printf("%d\n",dp[n][m]);
34     }
35     return 0;
36 }

 

hdu 1712 ACboy needs your help


联系
我们