当前位置: 代码迷 >> 综合 >> HDU5115Dire Wolf(区间DP)
  详细解决方案

HDU5115Dire Wolf(区间DP)

热度:17   发布时间:2023-12-06 19:39:34.0

题目大意:

你是一个战士现在面对,一群狼,每只狼都有一定的主动攻击力和附带攻击力。你杀死一只狼。你会受到这只狼的(主动攻击力+旁边两只狼的附带攻击力)这么多伤害~现在问你如何选择杀狼的顺序使的杀完所有狼时,自己受到的伤害最小。(提醒,狼杀死后就消失,身边原本相隔的两只狼会变成相邻,而且不需要考虑狼围城环这种情况)


思路:

枚举区间内最后一个被杀的狼

#include<bits/stdc++.h>
using namespace std;
const int maxn = 205;
int a[maxn], b[maxn], dp[maxn][maxn];
int main()
{int n, T;scanf("%d", &T);for(int kase = 1; kase <= T; kase++){scanf("%d", &n);for(int i = 1; i <= n; i++)scanf("%d", &a[i]);for(int i = 1; i <= n; i++)scanf("%d", &b[i]);for(int i = 1; i <= n; i++)for(int j = i; j <= n; j++)dp[i][j] = 0x3f3f3f3f;for(int len = 0; len <= n; len++)for(int i = 1; i +len <= n; i++)for(int k = i; k <= i+len; k++){int j = i + len;dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k+1][j] + a[k] + b[i-1] + b[j+1]);}printf("Case #%d: %d\n", kase, dp[1][n]);}return 0;
}