HDU 5115 – Dire Wolf [区间DP]

点击打开HDU题目链接

题意

给你N个怪物,知道他们的原始攻击力和附加攻击力,附加攻击力是指对左右旁边的帮助攻击力。问你杀掉所有的怪物最少需要花费多少总力量

分析

比赛的时候没想到是DP啊,以为已经有个DP了不可能还有一个,果然还是自己太水了。这道题区间DP对于每个区间[i, j]所需要的最小的攻击力要看最后杀死谁,设最后杀死的是k,则dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k+1][j] + b[i-1] + b[j+1]);由于所有怪物最后都要杀死,所以把原始攻击力求和加上最后的dp[1][n]就是最终答案

CPP代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 256, inf = 0x3f3f3f3f;
int n, a[maxn], b[maxn], dp[maxn][maxn];

int main() {
    int T, kase = 0; scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        int sum = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", a + i);
            sum += a[i];
        }
        memset(b, 0, sizeof(b));
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; ++i)
            scanf("%d", b + i);
        for(int i = 1; i <= n; ++i) {
            dp[i][i] = b[i-1]+b[i+1];
            for(int j = i + 1; j <= n; ++j)
                dp[i][j] = inf;
        }
        for(int d = 1; d <= n; ++d) {
            for(int i = 1; i + d <= n; ++i) {
                int j = i + d;
                for(int k = i; k <= j; ++k)
                    dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k+1][j] + b[i-1] + b[j+1]);
            }
        }
        printf("Case #%d: %d\n", ++kase, dp[1][n] + sum);
    }
    return 0;
}

欢迎留言