蓝桥杯：合并石子（区间DP+平行四边形优化）

http://lx.lanqiao.cn/problem.page?gpid=T414

题意：……

思路：很普通的区间DP，但是因为n<=1000，所以O（n^3）只能拿90分。上网查了下了解了平行四边形优化：地址。

但是看不懂。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const LL INF = 100000000000000000LL;
 5 LL dp[1010][1010], s[1010][1010];
 6 LL sum[1010];
 7 int main() {
 8     LL ans = 0;
 9     int n; scanf("%d", &n);
10     for(int i = 1; i <= n; i++) scanf("%lld", &dp[i][i]), sum[i] = sum[i-1] + dp[i][i], dp[i][i] = 0, s[i][i] = i;
11     for(int len = 1; len < n; len++) {
12         for(int l = 1; l + len <= n; l++) {
13             int r = l + len;
14             dp[l][r] = INF;
15             for(int k = s[l][r-1]; k <= s[l+1][r]; k++) {
16                 LL now = dp[l][k] + dp[k+1][r] + sum[r] - sum[l - 1];
17                 if(dp[l][r] > now) dp[l][r] = now, s[l][r] = k;
18             }
19         }
20     }
21     printf("%lld
", dp[1][n]);
22     return 0;
23 }