一开始写了一个复杂度很大的方法，然后还过了（千万记得开longlong ）
#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;typedef long long ll;
const int MAXN = 20;
ll f[MAXN][MAXN][MAXN];
int s[MAXN], n, k;int main()
{scanf("%d%d", &n, &k);REP(i, 1, n + 1) {int x;scanf("%d", &x);s[i] = s[i-1] + x;}REP(i, 1, n + 1)REP(j, i, n + 1)f[i][j][0] = s[j] - s[i-1];ll ans = f[1][n][0];REP(r, 1, k + 1){REP(d, 2, n + 1)for(int st = 1; st + d - 1 <= n; st++){int i = st, j = st + d - 1;REP(p, i, j)REP(u, 0, r)f[i][j][r] = max(f[i][j][r], f[i][p][u] * f[p+1][j][r-u-1]);}ans = max(ans, f[1][n][r]);}printf("%lld\n", ans);return 0;
}
然后看题解发现可以简化很多
#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;typedef long long ll;
const int MAXN = 20;
ll f[MAXN][MAXN], s[MAXN];
int n, k;int main()
{scanf("%d%d", &n, &k);REP(i, 1, n + 1) {ll x;scanf("%lld", &x);s[i] = s[i-1] + x;f[i][0] = s[i];}REP(r, 1, k + 1)REP(i, r + 1, n + 1)for(int j = i; j >= r + 1; j--){f[i][r] = max(f[i][r], f[j-1][r-1] * (s[i] - s[j - 1]));f[i][r] = max(f[i][r], f[j-1][r-1] + (s[i] - s[j - 1]));}printf("%lld\n", f[n][k]);return 0;
}为什么前面几道题要分i到j，而这道题可以只用从1到i呢？
仔细想一想，发现这道题的“后面几堆”可以直接表示出来，不需要用到之前算的f数组， 可以一路推下去。
前两道“后面几堆”需要用到f数组，那么就需要区间这样去做