程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 12563 Jin Ge Jin Qu hao(DP)

UVA 12563 Jin Ge Jin Qu hao(DP)

編輯:C++入門知識

UVA 12563 Jin Ge Jin Qu hao(DP)


 

 

思路:DP,用01背包的思路,每次記錄下每個時間的最大歌曲數,最後找答案先滿足歌曲數最大,在滿足時間最大

 

 

#include 
#include 
#include 
using namespace std;

const int N = 55;

int T, n, t, sing[N], dp[11005];

int main() {
	int cas = 0;
	scanf(%d, &T);
	while (T--) {
		scanf(%d%d, &n, &t);
		for (int i = 0; i < n; i++)
			scanf(%d, &sing[i]);
		sing[n++] = 678;
		memset(dp, -1, sizeof(dp));
		dp[0] = 0;
		for (int i = 0; i < n; i++) {
			for (int j = min(t - 1, 10000); j >= 0; j--) {
				if (dp[j] != -1)
					dp[j + sing[i]] = max(dp[j + sing[i]], dp[j] + 1);
   			}
  		}
  		int ans1 = 0, ans2;
  		for (int i = 11000; i >= 0; i--) {
  			if (ans1 < dp[i]) {
  				ans1 = dp[i];
 				ans2 = i;
     		}
    	}
    	printf(Case %d: %d %d
, ++cas, ans1, ans2);
 	}
	return 0;
}


 

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