57 lines
1014 B
C++
57 lines
1014 B
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
|
||
int a[101];
|
||
int sum[101]; // prefix sum
|
||
int f[101][101];
|
||
/*
|
||
|
||
区间动态规划解题步骤：
|
||
1.根据问题推测dp[i][j]的含义
|
||
问题是：把第1堆到第n堆石子合成一堆，最小的得分
|
||
dp[i][j]的含义：把第i堆到第j堆石子合成一堆，最小的得分
|
||
2.根据规则推出dp[i][j]的状态转移公式
|
||
在i-j之间选一个中间值k，
|
||
dp[i][j] = dp[i][k] + dp[k+1][j] + ( sum[j] - s[i-1] );
|
||
3.边界问题（比如设定dp[0][0],dp[0][j],dp[i][0],dp[i][j],dp[i][i]初始值）
|
||
|
||
*/
|
||
|
||
/*
|
||
input
|
||
7
|
||
13
|
||
7
|
||
8
|
||
16
|
||
21
|
||
4
|
||
18
|
||
|
||
output
|
||
239
|
||
*/
|
||
int main() {
|
||
ios::sync_with_stdio(false);
|
||
cin.tie(0);
|
||
int n;
|
||
cin>>n;
|
||
|
||
for(int i=1; i<=n; i++) {
|
||
cin>>a[i];
|
||
sum[i] = sum[i-1] + a[i];
|
||
}
|
||
|
||
for(int i=n-1; i>=1; i--) { //一定要逆序
|
||
for(int j=i+1; j<=n; j++) {
|
||
f[i][j] = INT_MAX;
|
||
for(int k=i; k<=j-1; k++) {
|
||
f[i][j] = min(f[i][j], f[i][k]+f[k+1][j] + sum[j]-sum[i-1]);
|
||
}
|
||
}
|
||
}
|
||
|
||
cout<<f[1][n]<<endl;
|
||
return 0;
|
||
}
|