HDU 1712 ACboy needs your help (分组背包模版题)-白红宇

HDU 1712 ACboy needs your help (分组背包模版题)

阅读量：5324 次

发布时间：2019-06-14

本文共 1007 字，大约阅读时间需要 3 分钟。

题目链接：

有n门课，和m天时间。每门课上不同的天数有不同的价值，但是上过这门课后不能再上了，求m天里的最大价值。

分组背包模版题。

1     //#pragma comment(linker, "/STACK:102400000, 102400000") 2     #include 
     
       3     #include 
      
        4     #include 
       
         5     #include 
        
          6     #include 
         
           7     #include 
          
            8 #include 
           
             9 #include 
            
             10 #include 
             
              11 #include 
              
               12 #include 
               13 using namespace std;14 typedef long long LL;15 typedef pair 
                
                  P;16 const int N = 1e2 + 5;17 int dp[N], a[N][N], inf = 1e6;18 19 int main()20 {21 int n, m;22 while(~scanf("%d %d", &n, &m) && (n || m)) {23 for(int i = 1; i <= n; ++i) {24 for(int j = 1; j <= m; ++j) {25 scanf("%d", &a[i][j]);26 dp[j] = 0;27 } 28 }29 for(int i = 1; i <= n; ++i) { //n组30 for(int j = m; j >= 1; --j) { //体积31 for(int k = 1; k <= m; ++k) { //第i组的各个数据32 if(j - k >= 0) {33 dp[j] = max(dp[j - k] + a[i][k], dp[j]);34 }35 }36 }37 }38 printf("%d\n", dp[m]);39 }40 return 0;41 }