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; }