帕秋莉的魔法
龙之吻—水货
2018-10-03 12:40:58
# 题外话
签到题就应该有签到题的样子，~~其实是我太菜了不会出难题~~，本来原来出的题就很水，想改难一点，结果就越来越简单了。
# Solution
其实题解并没有存在的意义，因为大家都会。
按题意进行dp状态设计，$f[i][j]$,表示以第$i$种魔法结束，咒语长度为$j$的最大威力。之后$2D1D$转移即可，时间复杂度$O(n^2m)$。
关于负数的问题，pascal选手可以直接忽略，其他选手平移一下就好了。
之后状态转移方程就是 ：
```cpp
f[i][j + a[i]] = std :: max(f[i][j + a[i]], f[k][j] + b[i] + w[k][i]);
```
总的代码就是：
```cpp
#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;
}
```