首页 > 代码库 > hdu5115 区间DP

hdu5115 区间DP

2024-08-11 19:39:18   219人阅读

题意：有n只狼，每只狼有两种属性，一种攻击力一种附加值，每杀一只狼

受到的伤害值为这只狼的攻击值与它旁边的两只狼的附加值的和，求把所有狼都杀光受到的最小的伤害值。

题解：还是老问题，，，区间DP想到了但是担心枚举i~j区间中元素时，处理dp[i][k-1]的时候要顾及i-1位置的狼，其实根本不用，初始化的时候已经顾及到了就说明全部都顾及到了，，，

真是菜

#include <cstdio>#include <cstring>#include <vector>#include <algorithm>#include <iostream>#include <map>#include <queue>#include <stack>#include <cmath>//#pragma comment(linker, "/STACK:102400000,102400000")using namespace std;#define PF(x) cout << "debug: " << x << " ";#define EL cout << endl;#define PC(x) puts(x);typedef long long ll;#define CLR(x, v) sizeof (x, v, sizeof(x))using namespace std;const int INF = 0x5f5f5f5f;const int  N= 2e5 + 10;const int mod=1e9 + 7;const int maxn = 210;using namespace std;int T,n;int dp[maxn][maxn],a[maxn],b[maxn];int main() {  // freopen("in.txt","r",stdin);    cin>>T;    int cas = 0;   while(T--){        cas++;        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 = 1;j <= n;j++)                dp[i][j] = 40000000+10;        for(int i = 1;i <= n;i++)            dp[i][i] = a[i] + b[i-1] + b[i+1];        //dp[0][0] = b[1],dp[n+1][n+1] = b[n];        for(int i = n - 1;i >= 1;i--)            for(int j = i + 1;j <= n;j++)                for(int k = i ;k <= j;k++){                    if(k == i)                        dp[i][j] = min(dp[i][j],dp[i+1][j]+a[i]+b[i-1]+b[j+1]);                    else if(k == j)                        dp[i][j] = min(dp[i][j],dp[i][j-1]+a[j]+b[i-1]+b[j+1]);                    else                    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",cas,dp[1][n]);   }    return 0;}

 

hdu5115 区间DP


联系
我们