程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ 3769 Diablo III(DP)

ZOJ 3769 Diablo III(DP)

編輯：C++入門知識

題意:給出13類裝備,每種裝備都有攻擊力和防御值,每種裝備只允許選擇一個,求滿足防御值至少在Ｍ的情況下,攻擊力最大為多少.

有幾個條件:13種裝備裡如果選擇了雙手裝備,就不能選擇武器和護盾了,還有戒指可以雙手各帶一個.

思路:首先不考慮條件,設dp[i][j]為前i種裝備,防御值達到j的時候的最大攻擊力.

那麼可以有dp[i][j + t] = max(dp[i][j + t], dp[i - 1][j] + d)這裡dp[i - 1][j]不等於-1,也就是必須先能達到這個防御值.

考慮雙手裝備的問題,可以把武器和護盾單獨作為一件雙手裝備或者把兩者合起來組合成一個雙手裝備,這樣條件就沒了.

考慮戒指的問題,選擇單個戒指就相當於只有一只手戴戒指,把戒指兩兩組合起來也就相當於雙手都帶了戒指,所以條件就都沒了.

不過這裡的Ｍ比較大,直接從第一類裝備開始遞推可能會超時,由於種類之間沒有關系所以從哪個種類開始遞推都沒有關系,所以這裡可以把種類按照裝備數量從大到小排序,把數量最大的種類作為遞推起點,這裡就可以省下很多時間,具體看代碼.

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int MAX = 301;
struct Equip{
	int d, t;
	Equip(int dd = 0, int tt= 0){
		d = dd;
		t = tt;
	}
};

mapmp;
void init(){
	mp["Head"] = 1;
	mp["Shoulder"] = 2;
	mp["Neck"] = 3;
	mp["Torso"] = 4;
	mp["Hand"] = 5;
	mp["Wrist"] = 6;
	mp["Waist"] = 7;
	mp["Legs"] = 8;
	mp["Feet"] = 9;
	mp["Finger"] = 10;
	mp["Shield"] = 12;
	mp["Weapon"] = 13;
	mp["Two-Handed"] = 11;
}



bool cmp(const vector & lhs, const vector & rhs){
	return lhs.size() > rhs.size();
}
int main(int argc, char const *argv[]){
	vector equip[14];
	int dp[12][50001];
	int T;
	init();
	scanf("%d", &T);
	while(T--){
		int N, M, ans = -1;
		scanf("%d%d", &N, &M);

		for(int i = 1; i <= 13; ++i){
			equip[i].clear();
		}

		for(int i = 1; i <= N; ++i){
			char name[12];
			int d, t, p;
			scanf("%s%d%d", name, &d, &t);
			p = mp[name];
			equip[p].push_back(Equip(d, t));
			if(p == 12 || p == 13){//把護盾和武器單個放在雙手武器裡.
				equip[11].push_back(Equip(d, t));
			}
		}

		vector tmp;
		for(int i = 0; i < equip[10].size(); ++i){
			tmp.push_back(equip[10][i]);//只帶單個戒指
			for(int j = i + 1; j < equip[10].size(); ++j){//帶兩個戒指
				tmp.push_back(Equip(equip[10][i].d + equip[10][j].d, equip[10][i].t + equip[10][j].t));
			}
		}
		equip[10].swap(tmp);
		tmp.clear();

		for(int i = 0;i < equip[12].size(); ++i){
			for(int j = 0; j < equip[13].size(); ++j){//把護盾和武器組合放到雙手武器裡
				equip[11].push_back(Equip(equip[12][i].d + equip[13][j].d, equip[12][i].t + equip[13][j].t));
			}
		}

		sort(equip + 1, equip + 12, cmp);//按數量從大到小排序
		memset(dp, -1, sizeof(dp));
	
		for(int i = 0; i < equip[1].size(); ++i){//數量最大的作為遞推起點,省去很多時間(TLE->AC)
			Equip e = equip[1][i];
			int nm = e.t;
			if(nm > M)nm = M;
			dp[1][nm] = max(dp[1][nm], e.d);
		}
		for(int i = 2; i <= 11; ++i){
			int size = equip[i].size();//常數優化
			for(int j = 0; j <= M; ++j){
				if(dp[i - 1][j] != -1){
					dp[i][j] = max(dp[i][j], dp[i - 1][j]);
					for(int k = 0; k < size; ++k){
						Equip e = equip[i][k];
						int nm = j + e.t;
						if(nm > M)nm = M;
						dp[i][nm] = max(dp[i][nm], dp[i - 1][j] + e.d);
					}
				}
			}
		}

		printf("%d\n", dp[11][M]);
	}	
	return 0;
}