帕秋莉的魔法

龙之吻—水货 · 2018-10-03 12:40:58 · 个人记录

题外话

签到题就应该有签到题的样子，其实是我太菜了不会出难题，本来原来出的题就很水，想改难一点，结果就越来越简单了。

Solution

其实题解并没有存在的意义，因为大家都会。

按题意进行dp状态设计，f[i][j],表示以第i种魔法结束，咒语长度为j的最大威力。之后2D1D转移即可，时间复杂度O(n^2m)。

关于负数的问题，pascal选手可以直接忽略，其他选手平移一下就好了。

之后状态转移方程就是 ：

f[i][j + a[i]] = std :: max(f[i][j + a[i]], f[k][j] + b[i] + w[k][i]);

总的代码就是：

#include<cstdio>
#include<cstring>
#include<algorithm>

const int maxn = 57;

int n, m, w[maxn][maxn];

int f[maxn][maxn * maxn * 2], ans, minn, maxx, mn;

struct Node {
    int a, b;

    Node (int a = 0, int b = 0) :
        a(a),
        b(b) {}
};
Node a[maxn];

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &a[i].a, &a[i].b);
        if (a[i].a > 0) {
            maxx += a[i].a;
        } else {
            minn += a[i].a;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &w[i][j]);
        }
    }
    memset(f, 0x8f, sizeof(f));
    ans = mn = f[1][1];
    f[0][maxn * maxn] = 0;
    maxx += maxn * maxn;
    minn += maxn * maxn;
    for (register int i = 1; i <= n; i++) {
        for (register int k = 0; k < i; k++) {
            for (register int j = minn; j <= maxx; j++) {
                if (f[k][j] == mn) {
                    continue;
                }
                f[i][j + a[i].a] = std :: max(f[i][j + a[i].a], f[k][j] + a[i].b + w[k][i]);
            }
        }
    }
    for (int i = 0; i <= n; i++) {
        ans = std :: max(ans, f[i][m + maxn * maxn]);
    }
    if (ans <= mn) {
        printf("-1\n");
        return 0;
    }
    printf("%d\n", ans);
    return 0;
}