- 1#include 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\n", dp[1][n]);
- 22
- return 0;
- 23
- }
来源: http://www.bubuko.com/infodetail-2011227.html