[TIOJ] 1883. pD. 最終幻想

題目連結:http://tioj.infor.org/problems/1883
本題看起來很0/1背包吧,不過它跟普通的0/1背包不同的點在於它的物品是無限個的,因此這類問題又被稱作完全背包問題,那完全背包問題該如何做呢,不難發現原本0/1背包問題在滾動的時候要從後面滾是為了維護它不會重複取,不過我們現在不就是要讓它能重複取嗎?,所以其實就把0/1背包原本從後面倒過來做的,改成從前面做就好了
#include <bits/stdc++.h>
using namespace std;

struct skill{
	int cost, damage;
};
skill mySkills[1000 + 5];
int dmg[10000 + 5];

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int w,b,n,m;
		scanf("%d%d%d",&w,&b,&n);
		for(int i=0;i<=w;i++){
			dmg[i]=0;
		}
		for(int i=0;i<n;i++){
			scanf("%d%d",&mySkills[i].cost,&mySkills[i].damage);
		}
		scanf("%d",&m);
		for(int i=0;i<n;i++){
			mySkills[i].cost+=m;
		}
		for(int i=0;i<n;i++){
			for(int j=mySkills[i].cost;j<w;j++){
				dmg[j] = max(dmg[j], dmg[j-mySkills[i].cost]+mySkills[i].damage);
			}
		}
		if(dmg[w-1] >= b)
			puts("Yes");
		else
			puts("No");
	}
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology