【每日一题】7月29日题目精讲—Max Power
Max Power
https://ac.nowcoder.com/acm/problem/20663
思路：
首先，每一列如果要学应该是学一个从上到下的连续区间，第二，当前这一列最多比右边的那一列多学一个——所以，考虑从右往左一列一列转移：
f[i][j][k]表示前i列一共选了k个技能学，第i列选了连续的前j个，
f[i][j][k] = max(f[i-1][p][k-j] + sum[i][j])
其中：sum[i][j]是列前缀和，表示第i列前j个数字的和；p从j-1枚举到n-i+1枚举，即第i-1列最少只比第i列少选一个（最多则可以选完）。
f[i][j][k]表示前i列一共选了k个技能学，第i列选了连续的前j个，
f[i][j][k] = max(f[i-1][p][k-j] + sum[i][j])
其中：sum[i][j]是列前缀和，表示第i列前j个数字的和；p从j-1枚举到n-i+1枚举，即第i-1列最少只比第i列少选一个（最多则可以选完）。
#include<bits/stdc++.h>
using namespace std;
int sum1[105];int n,m;
int sum2[105][105];
long long dp[56][56][1305];//这个空间把握的死死的，开到60就超限，开51，52还一直wa，没想到错这。。。。。。。。。。。。
long long ans = 0;
void solve() {
ans = 0;
for (int i = n; i >= 1; i--) {
for (int j = 0; j <= n - i + 1; j++) {
for (int k = sum1[j]; k <= m; k++) {
for (int l = max(j-1,0 ); l < n - i + 1; l++) {
dp[i][j][k] = max(dp[i][j][k], dp[i + 1][l][k - j] + sum2[j][i]);//状态转移方程
}
ans = max(ans, dp[i][j][m]);
}
}
}
}
int main() {
while (cin >> n >> m) {
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) {
sum1[i] = sum1[i - 1] + i;
for (int j = 1; j <= n - i + 1; j++) {
cin >> sum2[i][j];
sum2[i][j] += sum2[i - 1][j];//列前缀和
}
}
solve();
cout << ans << endl;
}
return 0;
} 我真的是吐了，内存没开够大，找半天没找到错那。。。。。。。。。 这是我见过最恶心最难的dp。。。。。。。。。
毕竟菜的扣脚。
