【每日一题】7月29日题目精讲—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列少选一个（最多则可以选完）。

#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。。。。。。。。。

毕竟菜的扣脚。