区间dp入门

深藏阁楼爱情的钟 2022-03-19 07:07 224阅读 0赞

# 概念： #

**区间DP**就是区间上的DP，先算出小区间的最优解，再由小区间合并推出大区间的最优解。

# 典例： #

## 一、石子合并。 ##

### 1.[51Nod 1021 石子归并][51Nod 1021]（直线版） ###

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int INF=0x3f3f3f3f;
    const int maxn=1010;
    int n;
    int a[maxn],sum[maxn];
    int s[maxn][maxn],dp[maxn][maxn];
    
    int main()
    {
        scanf("%d",&n);
        sum[0]=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];
            s[i][i]=i; //初始化区间的最优分割点 
        }
        
        // 从小区间向大区间进行递推 
        for(int d=1;d<n;d++){ //枚举区间长度
            for(int i=1,j;(j=i+d)<=n;i++){ //枚举区间起点
                dp[i][j]=INF;
                for(int k=s[i][j-1];k<=s[i+1][j];k++){ //枚举切割点，构造状态转移方程 
                	//printf("k=%d\n",k);
    				if(dp[i][k]+dp[k+1][j]<dp[i][j]){
                        dp[i][j]=dp[i][k]+dp[k+1][j];
                        s[i][j]=k;
                    }
    			} 
    			//printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);
                dp[i][j]+=sum[j]-sum[i-1];  
                //printf("**dp[%d][%d]=%d,s[%d][%d]=%d\n",i,j,dp[i][j],i,j,s[i][j]);
            }
        }
        printf("%d\n",dp[1][n]);
        return 0;
    }

### 2. [51Nod 1022 石子归并 V2][51Nod 1022 _ V2] (环形) ###

和直线形差不多，我们需要处理出来间隔为n-1的所有可能，所以区间扩大为2\*n-1进行处理，然后取dp\[i\]\[i+n-1\]的最小值。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int INF=0x3f3f3f3f;
    const int maxn=1010;
    int n;
    int a[maxn],sum[2*maxn];
    int s[2*maxn][2*maxn],dp[2*maxn][2*maxn];
     
    int main()
    {
        scanf("%d",&n);
        sum[0]=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];
            s[i][i]=i; //初始化区间的最优分割点 
        }
        
        for(int i=n+1;i<2*n;i++){
        	sum[i]=sum[i-1]+a[i-n];
        	s[i][i]=i;
    	}
        // 从小区间向大区间进行递推 
        for(int d=1;d<n;d++){ //枚举区间长度
            for(int i=1,j;i<=2*n-d;i++){ //枚举区间起点
    			j=i+d;
    			dp[i][j]=INF;
                for(int k=s[i][j-1];k<=s[i+1][j];k++){ //枚举切割点，构造状态转移方程 
                	//printf("k=%d\n",k);
    				if(dp[i][k]+dp[k+1][j]<dp[i][j]){
                        dp[i][j]=dp[i][k]+dp[k+1][j];
                        s[i][j]=k;
                    }
    			} 
    			//printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);
                dp[i][j]+=sum[j]-sum[i-1];  
                //printf("**dp[%d][%d]=%d,s[%d][%d]=%d\n",i,j,dp[i][j],i,j,s[i][j]);
            }
        }
        int mn=INF;
        for(int i=1;i<=n;i++){
        	mn=min(mn,dp[i][i+n-1]);
    	}
        printf("%d\n",mn);
        return 0;
    }

二、括号匹配问题。

三、整数划分问题。

[51Nod 1021]: https://www.51nod.com/Challenge/Problem.html#problemId=1021
[51Nod 1022 _ V2]: https://www.51nod.com/Challenge/Problem.html#problemId=1022