首页 > 代码库 > UVAlive 10154：Dire Wolf 区间DP
UVAlive 10154：Dire Wolf 区间DP
Dire Wolf
题目链接：
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5073
题意：
有一排的狼，每只狼有一个基础攻击力a[i]，和一个加成值b[i]（可以给相邻的两只狼加b[i]点攻击力，这只狼死后就不加了），你每杀一只狼需要花费能量值（狼的当前攻击力），你杀了这只狼周围的狼会自动往中间聚集（即不会有空隙），求杀完n只狼所需要的最小花费。
题解：
设dp[i][j]为区间杀完区间[i,j]内的狼所需的最小花费，只要在区间[i,j]内找到一个点k使得dp[i,k-1]+dp[k+1,j]+b[i-1]+b[j+1]最小即可。
代码
#include<stdio.h>
#include<string.h>
const long long inf=100000000000000;
long long b[202],dp[202][202];
long long mmin(long long x,long long y)
{
return x<y?x:y;
}
void clean(int n)
{
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;++i)
for(int j=i;j<=n;++j)
dp[i][j]=inf;
}
void solve()
{
int T,n,w=0;
long long res,x;
scanf("%d",&T);
while(T--)
{
res=0;
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%lld",&x),res+=x;
for(int j=1;j<=n;++j)
scanf("%lld",&b[j]);
b[0]=b[n+1]=0;
clean(n);
for(int len=0;len<=n;++len)
{
for(int i=1;i+len<=n;++i)
{
int j=i+len;
for(int k=i;k<=j;++k)
dp[i][j]=mmin(dp[i][j],dp[i][k-1]+dp[k+1][j]+b[i-1]+b[j+1]);
}
}
printf("Case #%d: %lld\n",++w,dp[1][n]+res);
}
}
int main()
{
solve();
return 0;
}
UVAlive 10154：Dire Wolf 区间DP