程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> Hdu 1712 ACboy needs your help(DP_背包)

Hdu 1712 ACboy needs your help(DP_背包)

編輯:關於C語言

題目大意:給定n門課,再用m天復習這n門課,然後給定一個n*m的矩陣A,A[i][j]表示用j天復習第i門課獲得得收益。問用m天復習不同的課獲得的最大收益。

解題思路:本題本身沒什麼難度,但是數據給的很有迷惑性,一開始我認為1門課可以復習兩次,然後就把n*m個收益當成n*m件物品進行01背包處理,提交華麗麗地返回一個Wa。再看了一遍題目,糗,要求選不同的課,那這樣就是分組背包,保證這門課只能選一次復習。
     狀態轉移方程:dp[k] = min(dp[k],dp[k-j] + pro[i][j])(i表示第i門課程,k表示天數,pro[i[j[表示第i門用j天的收益).復雜度(O(n *m * m).這裡要注意天數的枚舉順序必須要從大到小,這樣才能保證每次計算所需要的狀態是前一次的,才能保證後效性。

測試數據:
 2 3
4 4 1
3 2 1

1 2
4 4

代碼:
[cpp]
#include <stdio.h> 
#include <string.h> 
#define MAX 110 
 
 
int n,m,ans,dp[MAX]; 
int pro[MAX][MAX]; 
 
 
int main() 

    int i,j,k,t; 
 
 
    while (scanf("%d%d",&n,&m),n+m) { 
 
        for (i = 1; i <= n; ++i)  
            for (j = 1; j <= m; ++j) 
                scanf("%d",&pro[i][j]); 
 
 
        memset(dp,0,sizeof(dp)); 
        for (i = 1; i <= n; ++i) 
            for (k = m; k >= 1; --k) 
                for (j = k; j >= 1; --j) 
                    if (dp[k-j] + pro[i][j] > dp[k]) 
                        dp[k] = dp[k-j] + pro[i][j]; 
         
                     
        for (ans = i = 0; i <= m; ++i)        
            if (dp[i] > ans) ans = dp[i]; 
        printf("%d\n",ans); 
    } 

 


摘自 ZeroClock

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved