文章目录

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5115
我一看到题是贪心。。。结果是区间dp。。。
题意：有n只狼，啥第i只狼需要a[i]+b[i-1]+b[i+1]的值，如果这只狼死了，旁边的狼会补上去（我想这就是不能用贪心的原因吧，因为要不上去，就感觉很复杂，只能暴力地枚举，那优化一哈的暴力枚举就是dp了嘛），求最小值？
老套路dp[i][j]表示[i,j]这段的最小值，然后枚举中间的断点k，杀第k只狼。而此时[i,k-1]和[k+1,j]的狼已经死了的，所以杀死第k只狼的cost=a[k]+b[i-1]+b[j+1]

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=200+5;
int a[maxn],b[maxn];
int dp[maxn][maxn];
int main()
{
	int T;
	cin>>T;
	for(int Case=1;Case<=T;Case++)
	{
		int N;
		cin>>N;
		a[N+1]=b[N+1]=0;
		for(int i=1;i<=N;i++)cin>>a[i];
		for(int j=1;j<=N;j++)cin>>b[j];
		memset(dp,0x3f,sizeof dp);
		for(int i=1;i<=N+1;i++)dp[i][i-1]=0;//因为杀第i只狼的时候会出现dp[i][i-1]，所以这里要初始化一哈 
		for(int i=1;i<=N;i++)dp[i][i]=a[i]+b[i-1]+b[i+1];
		for(int len=1;len<N;len++)
		for(int i=1;i+len<=N;i++)
		{
			int j=i+len;
			for(int k=i;k<=j;k++)//[i,k-1]和[k+1,j]的狼已经***掉了，所以k的左边是i-1，右边是[j+1]，所以他的cost是b[i-1]+b[j+1]+a[k] 
			dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+b[i-1]+b[j+1]+a[k]);
		}
		cout<<"Case #"<<Case<<": "<<dp[1][N]<<endl;
	}
}