博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
区间DP（区间最优解）题目讲解总结
阅读量：5788 次
发布时间：2019-06-18

本文共 12766 字，大约阅读时间需要 42 分钟。

1：给出一个括号字符串，问这个字符串中符合规则的最长子串的长度。

【分析】区间DP要覆盖整个区间，那么要求所有情况的并集。先想出状态方程：dp[i][j]：i ~ j区间内最大匹配数目输出：dp[0][n-1]（从0开始）区间DP最先想到的是就是：1.边界情况初始化2.for枚举区间长度，一般从第二个开始3.for枚举起点4.直接求得终点5.若括号匹配的情况，相当于外围是ok的，继续深入看内部，左端点右移&右端点左移+2（因为外围匹配，数目+2）6.一般情况就是枚举断点k，打擂台求匹配数目最大值7.输出整个区间的最大匹配数

 

【逆序枚举区间长度】

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      
                       #include
                       
                        #define debug() puts("++++")#define gcd(a,b) __gcd(a,b)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define fi first#define se second#define pb push_back#define sqr(x) ((x)*(x))#define ms(a,b) memset(a,b,sizeof(a))#define sz size()#define be begin()#define pu push_up#define pd push_down#define cl clear()#define lowbit(x) -x&x#define all 1,n,1#define rep(i,x,n) for(int i=(x); i<=(n); i++)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair
                        
                          P;const int INF = 0x3f3f3f3f;const LL LNF = 1e18;const int maxm = 1e6 + 10;const double PI = acos(-1.0);const double eps = 1e-8;const int dx[] = {-1,1,0,0,1,1,-1,-1};const int dy[] = { 0,0,1,-1,1,-1,1,-1};int dir[4][2] = { { 0,1},{ 0,-1},{-1,0},{ 1,0}};const int mon[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int mod = 10056;#define inf 0x3f3f3f3f#define ll long longconst int maxn = 10010;int t,n,m,a[maxn],x,y,w;int dp[110][110],ans;string s;int tot=0;/*[题意]：给出一个括号字符串，问这个字符串中符合规则的最长子串的长度。dp[i][j]:i~j区间内最大匹配数输出：dp[1][n]match:dp[i][j] = dp[i+1][j-1]+2;for(k:1..j)dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]);((()))()()()([]]))[)(([][][)end66406*/bool match(int L,int R){ return s[L]=='('&&s[R]==')' || s[L]=='['&&s[R]==']';}int main(){ while(cin>>s) { if(s=="end") break; ms(dp,0); n=s.size(); for(int i=n-1;i>=0;i--)//枚举区间长度 { for(int j=i+1;j
POJ - 2955 Brackets

 【顺序】

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      
                       #include
                       
                        #define debug() puts("++++")#define gcd(a,b) __gcd(a,b)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define fi first#define se second#define pb push_back#define sqr(x) ((x)*(x))#define ms(a,b) memset(a,b,sizeof(a))#define sz size()#define be begin()#define pu push_up#define pd push_down#define cl clear()#define lowbit(x) -x&x#define all 1,n,1#define rep(i,x,n) for(int i=(x); i<=(n); i++)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair
                        
                          P;const int INF = 0x3f3f3f3f;const LL LNF = 1e18;const int maxm = 1e6 + 10;const double PI = acos(-1.0);const double eps = 1e-8;const int dx[] = {-1,1,0,0,1,1,-1,-1};const int dy[] = { 0,0,1,-1,1,-1,1,-1};int dir[4][2] = { { 0,1},{ 0,-1},{-1,0},{ 1,0}};const int mon[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int mod = 10056;#define inf 0x3f3f3f3f#define ll long longconst int maxn = 10010;int t,n,m,a[maxn],x,y,w;int dp[110][110],ans;string s;int tot=0;/*[题意]：给出一个括号字符串，问这个字符串中符合规则的最长子串的长度。dp[i][j]:i~j区间内最大匹配数输出：dp[1][n]match:dp[i][j] = dp[i+1][j-1]+2;for(k:1..j)dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]);((()))()()()([]]))[)(([][][)end66406*/bool match(int L,int R){ return s[L]=='('&&s[R]==')' || s[L]=='['&&s[R]==']';}int main(){ while(cin>>s) { if(s=="end") break; ms(dp,0); n=s.size(); for(int l=1;l
括号匹配

 

2：给你一串数字，头尾不能动，每次取出一个数字，这个数字贡献=该数字与左右相邻数字的乘积，求一个最小值。

【分析】类似一维的矩阵连乘

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      
                       #include
                       
                        #define debug() puts("++++")#define gcd(a,b) __gcd(a,b)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define fi first#define se second#define pb push_back#define sqr(x) ((x)*(x))#define ms(a,b) memset(a,b,sizeof(a))#define sz size()#define be begin()#define pu push_up#define pd push_down#define cl clear()#define lowbit(x) -x&x#define all 1,n,1#define rep(i,x,n) for(int i=(x); i<=(n); i++)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair
                        
                          P;const int INF = 0x3f3f3f3f;const LL LNF = 1e18;const int maxm = 1e6 + 10;const double PI = acos(-1.0);const double eps = 1e-8;const int dx[] = {-1,1,0,0,1,1,-1,-1};const int dy[] = { 0,0,1,-1,1,-1,1,-1};int dir[4][2] = { { 0,1},{ 0,-1},{-1,0},{ 1,0}};const int mon[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int mod = 10056;#define inf 0x3f3f3f3f#define ll long longconst int maxn = 10010;int t,n,m,a[maxn],x,y,w;int dp[110][110],ans;string s;int tot=0;/*[题意]：给你一串数字，头尾不能动，每次取出一个数字，这个数字贡献=该数字与左右相邻数字的乘积，求一个最小值。//类一维矩阵连乘dp[i][j]:i~j区间内最小权值输出：dp[1][n]dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+a[i-1]*a[k]*a[j]);610 1 50 50 20 53650*/int main(){ while(~scanf("%d",&n)) { ms(dp,0);// for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int r=2;r<=n;r++) { for(int i=1;i+r-1<=n;i++) { int j=i+r-1; dp[i][j]=INF;// for(int k=i;k
POJ - 1651 Multiplication Puzzle

 

3：给你n天需要穿的衣服的样式，每次可以套着穿衣服，脱掉的衣服就不能再穿了，问至少要带多少条衣服才能参加所有宴会.

【分析】

dp[i][j]：i~j区间内所需最少衣服数目

输出：dp[1][n]

之后不再用到：

dp[i][j] = dp[i][j-1]+1;
之后还要用到并且把断点保留到终点：
dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j])

 

区间dp，dp[i][j]表示i~j天所需的最小数量。

考虑第j天穿不穿，如果穿的话那么 dp[i][j]=dp[i][j-1]+1;

如果不穿的话，那么需要有一个 k (i<=k<j)，第j天和第k天穿的衣服相同，将k+1~j-1衣服套着穿后全部脱掉，那么

dp[i][j]=dp[i][k]+dp[k+1][j-1]；

【顺序】

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      
                       #include
                       
                        #define debug() puts("++++")#define gcd(a,b) __gcd(a,b)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define fi first#define se second#define pb push_back#define sqr(x) ((x)*(x))#define ms(a,b) memset(a,b,sizeof(a))#define sz size()#define be begin()#define pu push_up#define pd push_down#define cl clear()#define lowbit(x) -x&x#define all 1,n,1#define rep(i,x,n) for(int i=(x); i<=(n); i++)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair
                        
                          P;const int INF = 0x3f3f3f3f;const LL LNF = 1e18;const int maxm = 1e6 + 10;const double PI = acos(-1.0);const double eps = 1e-8;const int dx[] = {-1,1,0,0,1,1,-1,-1};const int dy[] = { 0,0,1,-1,1,-1,1,-1};int dir[4][2] = { { 0,1},{ 0,-1},{-1,0},{ 1,0}};const int mon[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int mod = 10056;#define inf 0x3f3f3f3f#define ll long longconst int maxn = 10010;int t,n,m,a[500],x,y,w;int dp[500][500],ans;string s;int tot=0;/*[题意]：给你n天需要穿的衣服的样式，每次可以套着穿衣服，脱掉的衣服就不能再穿了，问至少要带多少条衣服才能参加所有宴会.41 2 1 2只需要先穿上1，然后再穿上2，再脱掉2，就穿着1了，接着此时没有2的衣服了，所以我们还需要一件2的衣服，所以最后总共是需要3件衣服。dp[i][j]：i~j区间内所需最少衣服数目输出：dp[1][n]之后不再用到dp[i][j] = dp[i][j-1]+1;之后还要用到并且把断点保留到终点dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j])241 2 1 271 2 1 1 3 2 1Case 1: 3Case 2: 4*/int main(){ int cas=1; scanf("%d",&t); while(t--) { scanf("%d",&n); ms(dp,0); for(int i=1;i<=n;i++) scanf("%d",&a[i]); rep(i,1,n) dp[i][i]=1; for(int r=2;r<=n;r++) { for(int i=1;i+r-1<=n;i++) { int j=i+r-1; dp[i][j] = dp[i][j-1]+1;//不需要上一场衣服 for(int k=i; k
LightOJ - 1422 Halloween Costumes

 

【逆序】

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      
                       #include
                       
                        #define debug() puts("++++")#define gcd(a,b) __gcd(a,b)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define fi first#define se second#define pb push_back#define sqr(x) ((x)*(x))#define ms(a,b) memset(a,b,sizeof(a))#define sz size()#define be begin()#define pu push_up#define pd push_down#define cl clear()#define lowbit(x) -x&x#define all 1,n,1#define rep(i,x,n) for(int i=(x); i<=(n); i++)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair
                        
                          P;const int INF = 0x3f3f3f3f;const LL LNF = 1e18;const int maxm = 1e6 + 10;const double PI = acos(-1.0);const double eps = 1e-8;const int dx[] = {-1,1,0,0,1,1,-1,-1};const int dy[] = { 0,0,1,-1,1,-1,1,-1};int dir[4][2] = { { 0,1},{ 0,-1},{-1,0},{ 1,0}};const int mon[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int mod = 10056;#define inf 0x3f3f3f3f#define ll long longconst int maxn = 10010;int t,n,m,a[500],x,y,w;int dp[500][500],ans;string s;int tot=0;/*[题意]：给你n天需要穿的衣服的样式，每次可以套着穿衣服，脱掉的衣服就不能再穿了，问至少要带多少条衣服才能参加所有宴会.41 2 1 2只需要先穿上1，然后再穿上2，再脱掉2，就穿着1了，接着此时没有2的衣服了，所以我们还需要一件2的衣服，所以最后总共是需要3件衣服。dp[i][j]：i~j区间内所需最少衣服数目输出：dp[1][n]之后不再用到dp[i][j] = dp[i][j-1]+1;之后还要用到并且把断点保留到终点dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j])241 2 1 271 2 1 1 3 2 1Case 1: 3Case 2: 4*/int main(){ int cas=1; scanf("%d",&t); while(t--) { scanf("%d",&n); ms(dp,0); for(int i=1;i<=n;i++) scanf("%d",&a[i]); //如果无脑安排的话dp[i][j]=j-i+1，也就是区间长度。 rep(i,1,n) rep(j,i,n) dp[i][j]=j-i+1; for(int i=n-1;i>=1;i--) { for(int j=i+1;j<=n;j++) { dp[i][j] = dp[i+1][j]+1;//不需要上一场衣服 for(int k=i+1; k<=j; k++) //考虑是不是可以将i那件衣服在k这个地方重复利用 if(a[k] == a[i])//如果将第k场的衣服保留到第j场 dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k+1][j]); } } printf("Case %d: %d\n",cas++,dp[1][n]);// }}
逆序

 

4：给出n个数，每个数要先进栈然后出栈，第i个出栈的数a，花费的价值是(i-1)*a.问所有的数出栈花费的最小价值。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      
                       #include
                       
                        #define debug() puts("++++")#define gcd(a,b) __gcd(a,b)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define fi first#define se second#define pb push_back#define sqr(x) ((x)*(x))#define ms(a,b) memset(a,b,sizeof(a))#define sz size()#define be begin()#define pu push_up#define pd push_down#define cl clear()#define lowbit(x) -x&x#define all 1,n,1#define rep(i,x,n) for(int i=(x); i<=(n); i++)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair
                        
                          P;const int INF = 0x3f3f3f3f;const LL LNF = 1e18;const int maxm = 1e6 + 10;const double PI = acos(-1.0);const double eps = 1e-8;const int dx[] = {-1,1,0,0,1,1,-1,-1};const int dy[] = { 0,0,1,-1,1,-1,1,-1};int dir[4][2] = { { 0,1},{ 0,-1},{-1,0},{ 1,0}};const int mon[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int mod = 10056;#define inf 0x3f3f3f3f#define ll long longconst int maxn = 10010;int t,n,m,a[500],sum[500],x,y,w;int dp[500][500],ans;int tot=0;/*[题意]：题意：有n个人排成一排要上台表演，每个人有一个屌丝值ai。第i个上台表演的人，他的不满意度为(i-1)*ai。现在有一个类似于栈的黑屋子，你可以让某些人进入这个黑屋子。这些人要按照排的顺序来，那么对于排在最前面的人，就有两个选择：（1）让他直接上台表演；（2）让他暂时进黑屋子。现在请你选择一个合理的调度顺序，使得最后的总不满意度最小？——建模后就是：给出n个数，每个数要先进栈然后出栈，第i个出栈的数a，花费的价值是(i-1)*a.问所有的数出栈花费的最小价值是多少？1 2 3 4 5 —— 205 4 3 2 10 4 6 6 4 = 205 4 3 2 2 —— 240 4 6 6 8 = 24-----------------------------------------------------------不妨设他是第k个出场的（1<=k<=j-i+1)，那么根据栈后进先出的特点，以及题目要求原先男的是排好序的，那么：：第 i+1 到 i+k-1 总共有k-1个人要比i先出栈，第 i+k 到 j 总共j-i-k+1个人在i后面出栈~我们首先可以把小黑屋看成一个栈，如果我们枚举区间第k个人是第一个上场的话，我们仍然不知道左右区间每个人的上场顺序，这样子左右区间就不是完全独立的了，不具备无后效性这个特点。 我们可以枚举第i个人是第k个上场的，那么区间[i+1,i+k−1]的k−1(j-i+1=i+k-1-i-1+1=k-1)个人一定是在i之前上场的，并且区间[i+k+1,j]的所有人一定是在i之后上场的，这样所有人的相对顺序就确定了. 对于子区间dp[i+k+1][j]，我们是把它单独处理的，也就是得到这个最优解时第一个上场的确实是第一个上场的，但是如果想要由它转移到dp[i][j],那么第一个人实际上是第k+1个上场的，第二个人实际上是第k+2个上场的......所以别忘了这种附加“属性”。dp[i][j]：第i个人到第j个人这段区间的最小花费输出：dp[1][n]枚举出场次序k(1<=k<=n)第i个人第k个出场：前k个人：dp[i+1][i+k-1]第k个人：(k-1)*a[i]后k个人：dp[i+k][j] + sum[j] - sum[i+k-1]*/int main(){ int cas=1; scanf("%d",&t); while(t--) { scanf("%d",&n); ms(dp,0);ms(sum,0); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum[i] = sum[i-1] + a[i]; } rep(i,1,n) rep(j,i+1,n) dp[i][j]=INF; for(int r=2;r<=n;r++) { for(int i=1;i+r-1<=n;i++) { int j=i+r-1; for(int k=1; k<=n; k++) { dp[i][j]=min(dp[i][j],dp[i+1][i+k-1]+dp[i+k][j]+(k-1)*a[i]+k*(sum[j]-sum[i+k-1])); } } } printf("Case #%d: %d\n",cas++,dp[1][n]); }}/*2　51 2 3 4 555 4 3 2 2 Sample OutputCase #1: 20Case #2: 24*/
You Are the One HDU - 4283

 

转载于:https://www.cnblogs.com/Roni-i/p/9416434.html

你可能感兴趣的文章
阿里架构师：程序员必须掌握的几项核心技术能力
查看>>
程序员常用的六大技术博客类
查看>>
Iceworks 2.8.0 发布，自定义你的 React 模板
查看>>
胖哥学SpringMVC:请求方式转换过滤器配置
查看>>
Kotlin 更加优雅的 Builder - 理解 with
查看>>
前端日拱一卒D6——字符编码与浏览器解析
查看>>
深入理解浏览器的缓存机制
查看>>
微软向Linux社区开放60000多项专利：对开源微软是认真的
查看>>
Hoshin Kanri在丰田的应用
查看>>
又拍云沈志华：如何打造一款安全的App
查看>>
克服大数据集群的挑战
查看>>
PostgreSQL并发控制（MVCC, 事务，事务隔离级别）
查看>>
DM***的第二阶段OSPF
查看>>
20180702搭建青岛RAC记录
查看>>
Spring Security OAuth 实现OAuth 2.0 授权
查看>>
linux文件及简单命令学习
查看>>
dubbo源码分析-架构
查看>>
新 Terraform 提供商: Oracle OCI, Brightbox, RightScale
查看>>
6套毕业设计PPT模板拯救你的毕业答辩
查看>>
IT兄弟连 JavaWeb教程 JSP与Servlet的联系
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-12-21 16:12:44   当前IP: 3.22.79.181   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我