各种DP

区间DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cstring>
using namespace std;
const int N=310;
const int INF=0x3f3f3f3f;
int s[N];
int f[N][N];

int main()
{
    int n; cin>>n;
    for(int i=1;i<=n;i++) cin>>s[i];
    for(int i=1;i<=n;i++) s[i]=s[i]+s[i-1];
    
    
    //区间DP的遍历方式！
    for(int len=2;len<=n;len++)//遍历长度！
    {
        for(int i=1;i+len-1<=n;i++)//遍历起点!
        {
            int l=i,r=i+len-1;
            f[l][r]=0x3f3f3f3f;
            for(int k=l;k<r;k++)//分界点！[l,k],[k+1,r]  k的范围l...r-1
            {
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
            }
        }
    }
    cout<<f[1][n];
}