区间dp

1.acwing 282石子合并问题

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n;
 5 const int N = 310;
 6 int s[N];
 7 int f[N][N];
 8 
 9 int main ()
10 {
11     scanf("%d", &n);
12     for (int i = 1; i <= n; i ++ ) scanf("%d", &s[i]);
13     
14     for (int i = 1; i <= n; i ++ ) s[i] += s[i - 1];
15     
16     //区间dp套路:从小到大枚举区间长度和区间起点,在枚举我们的决策
17     //如果len == 1,表示一堆，不需要合并，代价为0;
18     for (int len = 2; len <= n; len ++ )//按照长度从小到大枚举区间长度
19        for (int i = 1; i + len - 1 <= n; i ++ ) //枚举所有区间起点
20        {
21            int l = i, r = i + len - 1; //表示该区间的起点和终点
22            f[l][r] = 1e8;
23            for (int k = l; k < r; k ++ ) //表示该区间的分割点
24            f[l][r] = min(f[l][r],f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
25        }
26        
27      cout << f[1][n] << endl;
28      return 0;
29        
30 }