题意简述： 给出两个正整数数列 A1 , A2 , 序列长度分别为 L1 和 L2 (L1,L2≤2000) ，每次可以移除序列 A1 的最后 K1 个数（可以是整个序列）并得到它们的和 S1 , 同时移除序列 A2 的最后 K2 个数（可以是整个序列）并得到它们的和 S2 , 那么这次移动的费用为 (S1−K1)∗(S2−K2) , 直到两个序列都为空，这次游戏的费用就为每次移动费用的和。 题解： 首先 O(n2) 状态表示 f[i][j] 表示移动完序列 A1 前 i 个元素和 A2 前 j 个元素的最小费用，暴力转移就是 O(n2) 枚举每次转移的元素，不难发现每次转移一定有一边只有一个元素，否则可以将两边的各一个元素拿出来单独操作，费用会更小，转移就变成了 O(n) 。转移的时候其实是两个前缀取 min , 对于这两种前缀我们单独开两个数组维护，那么转移就变成 O(1) 了。
#include<bits/stdc++.h> typedef long long ll; const int N = 2017; const ll INF = 1e15; template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f *= -1; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } int n, m, a[N], b[N]; ll f[N][N], g[N][N], h[N][N]; void cmin(ll &a, const ll &b) {if (b < a) a = b;} int main() { freopen("game.in", "r", stdin); freopen("game.out", "w", stdout); scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) read(a[i]), --a[i]; for (int i = 1; i <= m; i++) read(b[i]), --b[i]; for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) f[i][j] = g[i][j] = h[i][j] = INF; f[0][0] = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { ll t = (ll)a[i] * b[j]; g[i][j] = std::min(g[i - 1][j] + t, f[i - 1][j - 1] + t); h[i][j] = std::min(h[i][j - 1] + t, f[i - 1][j - 1] + t); f[i][j] = std::min(h[i][j], g[i][j]); } printf("%lld\n", f[n][m]); return 0; }