2017百度之星 资格赛 1003 度度熊与邪恶大魔王

2017年8月5日

dp[i][j]表示消灭防御力为i,生命值为j所需要的最少晶石.

那么就可以有dp[i][j] = min(dp[i][j], dp[i][j - (p[c] - i)] + k[c]);

计算出 dp[i][j]后,把n个怪物的防御力,生命值作为dp的下标,求和就可以得到答案了.

注意答案要用long long,否则会越界.

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 100005;
long long dp[15][1005];
int a[N], b[N];
int p[1005], k[1005];
int main()
{
    int n, m;
    while (~scanf("%d %d", &n, &m)) {
        for (int i = 1; i <= n; i++) {
            scanf("%d %d", a + i, b + i);
        }
        int mx = 0;
        for (int i = 0; i < m; i++) {
            scanf("%d %d", k + i, p + i);
            mx = max(mx, p[i]);
        }
        int ok = 0;
        for (int i = 1; i <= n; i++) {
            if (mx <= b[i]) {
                ok = 1;
                break;
            }
        }
        if (ok) {
            printf("-1\n");
            continue;
        }
        memset(dp, INF, sizeof(dp));
        for (int i = 0; i <= 10; i++) {
            dp[i][0] = 0;
            for (int j = 0; j <= 1005; j++) {
                for (int c = 0; c < m; c++) {
                    if (p[c] <= i)
                        continue;
                    if (j - (p[c] - i) >= 0)
                        dp[i][j] = min(dp[i][j], dp[i][j - (p[c] - i)] + k[c]);
                    else
                        dp[i][j] = min(dp[i][j], 1LL * k[c]);
                }
            }
        }
        long long ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += dp[b[i]][a[i]];
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注