首页 > 其他分享 >区间dp

区间dp

时间:2022-11-12 13:22:26浏览次数:72  
标签:return int sum 区间 include dp

区间dp:顾名思义,就是从小的区间推向大的区间。
区间dp的一般模板:

for(int len = 1;len<=n;len++)
{
    for(int j = 1;j+len<=n+1;j++)
    {
         int r = j+len - 1;
         for(int l = j;l<r;l++)
         {
                dp[j][r] = min(dp[j][r],dp[j][l]+dp[l+1][r]+number);//这里的number需要具体问题及具体分析。
         }
    }
}

我们以合并石子为例:

合并石子

做法:我们在看到这道题时主要的点就是不知道合并石子的顺序,枚举所有的区间,然后暴力所有的合并情况(这一个区间内哪一个石子最后合并进去)。

我们需要枚举哪些石子堆先合并,所以我们要从小到大枚举出所有的长度,然后再依次枚举所有状态即可,下面是参考代码:

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int inf = 0x3f3f3f3f;
const int N = 1e4 + 7;

int a[N], sum[N];
int cal(int l, int r) {
    return sum[r] - sum[l - 1];
}
int dp[N][N];

signed main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];//前缀
    }
    for (int len = 1; len <= n; len++) {
        for (int l = 1; l + len <= n; l++) {
            int r = l + len;
            dp[l][r] = inf;
            for (int k = l; k <= r; k++) {
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + cal(l, r));
            }
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}

当然,也有加强版的区间dp,如果区间dp成了环,那么代码应该就有所变化了,下面是环形石子合并代码:
戳我

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int inf = 0x3f3f3f3f;
const int N = 1e4 + 7;

int a[N], sum[N];
int cal(int l, int r) {
    return sum[r] - sum[l - 1];
}
int dp[N][N];
int f[N][N];
signed main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = n + 1; i <= n * 2; i++)
        a[i] = a[i - n];
    for (int i = 1; i <= n * 2; i++)
        sum[i] = sum[i - 1] + a[i];
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n * 2; l++) {
            int r = l + len - 1;
            dp[l][r] = inf;
            f[l][r] = -inf;
            for (int k = l; k < r; k++) {
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + cal(l, r));
                f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + cal(l, r));
            }
        }
    }
    int minx = inf, maxx = 0;
    for (int i = 1; i <= n; i++) {
        minx = min(minx, dp[i][i + n - 1]);
        maxx = max(maxx, f[i][i + n - 1]);
    }
    cout << minx << endl
         << maxx << endl;
    return 0;
}

相对于的普通的变化就是环形的情况下任意一堆都可以是第一堆,这个题也用了环形问题的通解,就是将数组扩大两倍。

我们现在再做几道例题:
例题1:括号匹配
题意:找到最大的括号匹配数
做法:区间dp,和那个石子合并类似,dp[i][j]就是表示[i,j]内能够匹配的最大数量,所以如果s[i]和s[j]要是能匹配的情况下,先将dp[i][j]=dp[i+1][j-1]+2,完成初始的赋值(表示第一个括号和最后一个匹配),然后依次枚举区间即可。
下面是AC代码:

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[105][105];
int main()
{
    char s[105];
    while(scanf("%s",s+1)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        int len = strlen(s+1);
        if(s[1]=='e')break;
        for(int l = 1;l<=len;l++){
            for(int i = 1;i+l<=len+1;i++){
                int j= i+l-1;
                if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']')){//如果匹配,先更新,不然的话无法实现最左边括号匹配的状态
                    dp[i][j] = dp[i+1][j-1]+2;
                }
                for(int k = i;k<j;k++)
                {
                    dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]);
                }
            }
        }
        cout<<dp[1][len]<<endl;
    }
    return 0;
}

例题2:整数划分(四)
这个和那个合并石子有些不同的,我们可以将所有的操作看作是在区间[1,len]之内进行,所以我们可以将dp[i][j]表示为在[1,i]上进行操作然后放了j和括号的最大值,这样我们需要枚举三层,第一层是乘号的数量,第二层是区间,第三层是将最后一个乘号放在那个数的后面。
下面是参考的AC代码:

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
ll dp[50][50];
ll num[50][50];
int main()
{
    int T;
    scanf("%d",&T);
    char s[100];
    while(T--)
    {
        int m;
        scanf("%s%d",s+1,&m);
        int len = strlen(s+1);
        memset(dp,0,sizeof(dp));
        memset(num,0,sizeof(num));
        for(int i = 1; i<=len; i++)
        {
            for(int j = i; j<=len; j++)
            {
                for(int k = i;k<=j;k++){
                    num[i][j]*=10;
                    num[i][j]+=(s[k]-'0');
                }
            }
            dp[i][0] = num[1][i];
        }
        for(int j = 1;j<m;j++){//枚举乘号的个数,这个尽量在最外层枚举,比较好写,也符合我们对于第三维的定义,枚举第j个放在哪,也可以样理解,我第三位枚举的是位置,所有一定是在某个位置后面,我只能放一个,所以这个不能放在第三维,但是可以放在第二维。
            for(int i = 1;i<=len;i++){//枚举长度
                for(int k = 1;k<i;k++){//在哪个整数后面放上乘号,注意不能放到最一个数的后面
                    dp[i][j] = max(dp[i][j],dp[k][j-1]*num[k+1][i]);
                }
            }
        }
        cout<<dp[len][m-1]<<endl;//输出在1~len插入m-1个乘号的结果
    }
    return 0;
}

下面是几道较难的区间dp
Link with Bracket Sequence II
题解:就是找到所有的括号匹配的种类。下面是AC代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int mod=1e9+7;
int n,m;
int a[550];
int dp[550][550];
int dfs(int l,int r)
{
    if((r-l+1)%2) return 0;//奇数个括号
    if(r-l+1==0) return 1;
    if(r-l+1==2)
    {
        if(a[l]>0&&a[r]==-a[l]) return 1;
        else if(a[l]==0&&a[r]<0) return 1; 
        else if(a[l]>0&&a[r]==0) return 1;
        else if(a[l]==0&&a[r]==0) return m;
        else return 0;
    }
    if(dp[l][r]!=-1) return dp[l][r];//记忆化搜索
    int res=0;
    if(a[l]>0)
    {
        for(int i=l+1;i<=r;i+=2)
        {
            if(a[i]==-a[l]||a[i]==0) res=(res%mod+(dfs(l+1,i-1)%mod*dfs(i+1,r)%mod)%mod);
        }
    }
    else if(a[l]==0)
    {
        for(int i=l+1;i<=r;i+=2)//枚举区间长度的过程,必须都是偶数,这里也类似于剪了一个小枝条
        {
            if(a[i]<0) res=(res%mod+(dfs(l+1,i-1)%mod*dfs(i+1,r)%mod)%mod)%mod;
            if(a[i]==0) res=(res%mod+(m%mod*dfs(l+1,i-1)%mod*dfs(i+1,r)%mod)%mod)%mod;
        }
    }
    return dp[l][r]=res;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=n;j++)
            {
                dp[i][j]=-1;
            }
        }
        for(int i=1;i<=n;i++) cin>>a[i];
        cout<<dfs(1,n)%mod<<endl;
    }
    return 0;
}

详细题解请戳我

还有就几道题现在找不到了,而且区dp还有四边形优化,持续更新中~~~~~~

标签:return,int,sum,区间,include,dp
From: https://www.cnblogs.com/kingwz/p/16883547.html

相关文章

  • P3226 [HNOI2012]集合选数(状压 DP)
    P3226[HNOI2012]集合选数要求选出集合\(S\)满足如果\(x\)选择了,\(2x\)和\(3x\)都不能选择。求\(\{1,2,\dots,n\}\)的符合要求的子集数量。\(n\le10^5\)。......
  • 基于QPSK+LDPC的微波信道误码率matlab仿真
    目录一、理论基础二、核心程序三、测试结果FPGA教程目录MATLAB教程目录一、理论基础  1.1QPSKQPSK数字解调包括:模数转换、抽取或插值、匹配滤波、时钟和载......
  • UDP --02--UDP广播数据
    设计模型局域网UDP广播数据端UdpBroadCast.cpp #include<tchar.h>//_T宏#include<stdio.h>//printfsprintf#include<iostream>//coutfstreamusingnamespacestd;......
  • 如何检测UDP 端口是否连接成功?
    (转,仅作为个人学习备用,原文地址: https://blog.51cto.com/kusorz/1749878)根据测试环境的不同,用户可以参阅如下方式测试UDP端口的连通性。假设待测试服务器的IP地址为1.1.......
  • 线段树维护区间历史版本和
    好久没写博客了,主要是这玩意网上有点难搜到,就干脆糊了一个另外区间加操作的题见这个博客给定长为\(n\)的01序列,\(m\)个询问,第\(i\)次认为产生一个新版本\(i\);要......
  • Apple开发_Socket_UDP协议广播机制的实现
    1、前言1.1什么是UDP协议广播机制?举一个例,例如在一群人群中,一个人要找张三,于是你向人群里大喊一声(广播):“谁是张三”如果它是张三,它就会回应你,在网络中也是一样的......
  • ABC 267 D - Index × A(Not Continuous ver.) (DP)
    https://atcoder.jp/contests/abc267/tasks/abc267_d题目大意:给定长度为n的数组a,让我们从中选择m个数字,按顺序组成B(a1----am)之后,sum=1*a1+……+m*am;问我们sum最大......
  • 在关闭RDP远程连接后,保持windows程序的运行
    问题在最近将笔记本放在了宿舍24小时开机由于挂网课,在教室里可以用微软RDClientapp连接宿舍里的电脑查看刷课进度。但是在几次连接后发现,在ipad端关闭'RDP'远程连接后,笔......
  • 单调队列优化DP
    [POI2015]WIL题目描述给定一个长度为\(n\)的序列,你有一次机会选中一段连续的长度不超过\(d\)的区间,将里面所有数字全部修改为\(0\)。请找到最长的一段连续区间,使得......
  • Java多线程 ThreadPoolExecutor-RejectedExecutionHandler拒绝执行策略
    目录​​一、说明​​​​二、理解​​​​三、实现​​​​1.AbortPolicy​​​​2.DiscardPolicy​​​​3.DiscardOldestPolicy​​​​4.CallerRunsPolicy​​​​5.自......