HDU5115 Dire Wolf 區間DP 記憶化搜索

HDU5115 Dire Wolf 區間DP 記憶化搜索

題意：舉個例子，就跟DOTA裡的狼BB一樣，自身有攻擊力，還有光環可以提升同伴的攻擊力，狼站成一排，光環只能提供給相鄰的狼，打掉一直狼需要打一下，同時它也會打一下，這樣你的扣血量其實就等於該狼的攻擊力

方程很好想，dp[i][j]代表 打掉區間[i,j]內的狼所需最少血量，這裡是閉區間，後來看到是200*200 ，那麼就懶得去想方程轉移了，直接記憶化搜索就可以了，注意點是 一個狼被宰了，它相鄰兩邊的兩只狼攻擊力會減少，所以搜索過程 分區間搜索時邊界要設定好，一開始沒弄好 結果 案例一直沒跑出來，這深搜調試起來還是比較麻煩的，直接由區間[i,j]裡面開始分著搜 [i,k - 1] [k + 1,j],一直分下去，這樣跑出來 700ms,題目給了5s，估計這題目有比較秒的方法 加上 暴力做出來的，

int t;

int n;

int aa[200 + 55],bb[200 + 55];

int dp[200 + 55][200 + 55];

int Case = 0;

void init() {
	memset(dp,-1,sizeof(dp));
	memset(aa,0,sizeof(aa));
	memset(bb,0,sizeof(bb));
}

bool input() {
	while(cin>>n) {
		for(int i=1;i<=n;i++)cin>>aa[i];
		for(int i=1;i<=n;i++)cin>>bb[i];
		return false;
	}
	return true;
}

int dfs(int l,int r) {
	if(dp[l][r] != -1)return dp[l][r];
	//cout<= i + 1)tmp += dfs(i + 1,r);
		now = min(now,tmp);
	}
	return dp[l][r] = now + bb[l - 1] + bb[r + 1];
}
 
void cal() {
	dfs(1,n);
	printf("Case #%d: ",++Case);
	cout<>t;
	while(t--) {
		init();
		if(input())return 0;
		cal();
		output();
	}
	return 0;
}