2018-Summer之区间dp

区间dp

什么是区间dp：
区间dp是解决区间上的一类动态规划问题的方法，例如区间合并、区间符号配对等等，其思想是将大区间分成小区间，结合动态转移方程来求小区间的最优解，最终合并成大区间的最优解

区间dp的一般思路
1.确定dp数组初始值
2.确定转移方程
3.枚举区间、分割点
4.dp[1][N]一般是最后答案
5.区间dp的复杂度一般为n^2，数据规模为几百

区间dp的一般模板：

int dp[maxn][maxn];
void init()
{for(int i=1;i<=n;i++)dp[i][i]=INF/0;//此处初始值视题目而定
}
for(int len=1;len<=n;len++)//枚举区间长度
{for(int i=1;i+len<=n;i++)//枚举区间起点{int j=len+i;//区间终点for(int k=i;k//枚举区间分割点dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);}
}

例题：https://vjudge.net/problem/HRBUST-1818

石子合并问题-直线版

给一行石子，两两相邻合并成新石子所得为得分，求最终得分最小和最大值

解题思路比较明了，区间i~j的转移方程为

最大值：
dp[n][n]初始化为0
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);

最小值：
dp[n][n]初始化为0(区间长度为1的情况)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);

#include
#include
#include
#define INF 0x3f3f3f3f
using namespace std;
int st[105];
int sum[105]={0};
int dp[205][205];
int dp2[205][205];
int main()
{int n;while(~scanf("%d",&n)){for(int i=1;i<=n;i++){scanf("%d",&st[i]);sum[i]=sum[i-1]+st[i];}memset(dp,0,sizeof(dp));memset(dp2,INF,sizeof(dp2));for(int i=1;i<=n;i++){dp[i][i]=0;dp2[i][i]=0;    }       for(int len=1;lenfor(int i=1;i+len<=n;i++){int j=i+len;for(int k=i;k1][j]+sum[j]-sum[i-1]);}for(int len=1;lenfor(int i=1;i+len<=n;i++){int j=i+len;for(int k=i;k1][j]+sum[j]-sum[i-1]);}cout<1][n]<<' '<1][n]<return 0;}

石子合并问题–圆形版

https://vjudge.net/problem/HRBUST-1819
这个问题和前一个差不多，只不过是由直线变成了圆形，直线变圆形的解决方案一般是把直线变成两倍

#include 
#include 
#include 
#include 
#include 
#define INF 0x3f3f3f3f
using namespace std;
int a[210];
int dp[500][500];
int sum[210];
int main(){int n;while(~scanf("%d", &n)){memset(dp, INF, sizeof(dp));for(int i=1; i<=n; i++){scanf("%d", &a[i]);a[i+n]=a[i];dp[i][i]=0;dp[i+n][i+n]=0;}sum[0]=0;for(int i=1; i<=n*2; i++){sum[i]=sum[i-1]+a[i];}for(int len=2; len<=n; len++){for(int i=1; i+len-1<=2*n; i++){int j=i+len-1;for(int k=i; k1][j]+sum[j]-sum[i-1]);}}}int ans=INF;    for(int i=1; i<=n; i++){ans=min(ans, dp[i][i+n-1]);}cout << ans << ' ';memset(dp, 0, sizeof(dp));for(int len=2; len<=n; len++){for(int i=1; i+len-1<=2*n; i++){int j=i+len-1;for(int k=i; k1][j]+sum[j]-sum[i-1]);}}}ans=0;for(int i=1; i<=n; i++){ans=max(ans, dp[i][i+n-1]);}cout << ans << endl;}return 0;
}

括号配对

https://vjudge.net/problem/POJ-2955
题意是给一行符号，其中（）是成对的，【】是成对的，问最多有多少对配对成立
思路是枚举区间，区间两头配对则加1

#include
#include
#include
using namespace std;
char s[300];
int dp[500][500]; 
char t[]={"end"};
int main()
{while(~scanf("%s",s)&&(strcmp(s,t)!=0)){   int l=strlen(s);memset(dp,0,sizeof(dp));for(int len=0;lenfor(int i=0;i+lenint j=i+len;if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']'))dp[i][j]=dp[i+1][j-1]+2;for(int k=i;k1][j]);}cout<0][l-1]<return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！