N - Slimes

原题链接：https://atcoder.jp/contests/dp/tasks/dp_n

题目大意：

石子合并问题。

解题思路：

区间dp就是先维护小区间，在扩展到大的区间。

代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define debug(a) cout<<#a<<":"<<a<<endl;
 5 const ll INF=0x3f3f3f3f3f3f3f3f;
 6 const ll N=1e6+7;
 7 const ll mod=1e9+7;
 8 ll maxn,minn;
 9 ll T,n,m;
10 ll arr[N];
11 ll sum[N];
12 ll dp[500][500];
13 
14 int main(){
15     ll a,len,flag;
16     ll ans=0;
17     memset(dp,INF,sizeof(dp));
18     cin>>n;
19     sum[0]=0;
20     for(int i=1;i<=n;i++){
21         scanf("%lld",arr+i);
22         sum[i]=sum[i-1]+arr[i]; 
23         dp[i][1]=0;
24     }
25     for(int i=2;i<=n;i++){
26         for(int j=1;j<=n-i+1;j++){
27             for(int k=1;k<i;k++){
28                 dp[j][i]=min(dp[j][i],dp[j][k]+dp[j+k][i-k]+sum[j+i-1]-sum[j-1]);
29             }
30         }
31     }
32     cout<<dp[1][n]<<endl;
33     return 0;
34 }