首页 > 其他分享 >区间DP

区间DP

时间:2024-05-25 14:55:50浏览次数:32  
标签:状态 min len DP 区间 dp

区间DP

区间DP的一般表达式:

枚举区间长度
枚举区间起点
计算区间终点
枚举区间断点

P1220 关路灯

状态

dp[i][j][0/1]表示区间[i,j]的路灯全关掉且站在i或j处的最小功耗

答案

min(dp[1][n][0],dp[1][n][1])

状态转移

for(int len=2;len<=n;len++){
	for(int i=1;i+len-1<=n;i++){ // 起点 
		int j=i+len-1;
		dp[i][j][0]=min(dp[i+1][j][0]+(x[i+1]-x[i])/*时间*/*(sum[i]+sum[n]-sum[j])/*功率之和*/,dp[i+1][j][1]+(x[j]-x[i])/*时间*/*(sum[i]+sum[n]-sum[j])/*功率之和*/);
		dp[i][j][1]=min(dp[i][j-1][0]+(x[j]-x[i])/*时间*/*(sum[i-1]+sum[n]-sum[j-1])/*功率之和*/,dp[i][j-1][i]+(x[j]-x[j-1])/*时间*/*(sum[i-1]+sum[n]-sum[j-1])/*功率之和*/);
	}
}

初始状态

dp[i][i]=abs(x[i]-x[c])*(sum[n]-w[c])

P4290 [HAOI2008] 玩具取名

样例解释

初始 过程1 结果
I WW IIII
N WW IIII

状态

dp[i][j][0/1/2/3]表示字符串区间[i,j]的字串可以由第0/1/2/3的字母替换而来。

辅助状态

yes[a][b][c]代表a可以用b和c替代。

答案

dp[1][n][0]输出w,dp[1][n][1]输出i ……

状态转移

for(int k=i;k<j;k++){
	for(int c1=0;c1<4;c1++){
		for(int c2=0;c2<4;c2++){
			for(int c=0;c<4;c++){
				if(dp[i][k][c1] && dp[k+1][j][c2]&&yes[c][c1][c2]){
					dp[i][j][c]=1;
				}
			}
		}
	}
}

初始状态

dp[i][i][s[i]]=1

P1435 [IOI2020] 回文子串

状态

dp[i][j]表示将区间[i,j]变成回文的最小操作次数;

答案

dp[i][n];

状态转移

dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;
if(s[i]==s[j]){
	dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
	if(len==2)dp[i][j]=0;
}

P1070 [NOIP2009 普及组] 道路游戏

状态

dp[i][j]表示时间为i,机器人处于位置j的到的最大金币数

状态转移

情况1:不换机器人
dp[i][j]=dp[i-1][j-1]+a[i][j]
情况2:更换机器人
dp[i][j]=max(dp[i-1][k]+a[i][j]-b[j],dp[i][j])

P1775 石子合并(弱化版)

状态

dp[i][j]表示从合并i到j所花费的最小代价

答案

dp[1][n]

状态转移

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);

CF607B Zuma

状态

dp[i][j]表示从i到j消除的最小时间

状态转移

for(int len=3;len<=n;len++){
    for(int i=1;i<=n-len+1;i++){
        int j=i+len-1;
        if(a[i]==a[j])dp[i][j]=dp[i+1][j-1];
        for(int k=i;k<j;k++){
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
        }
    }
}

P3205[HNOI2010]合唱队

状态

dp[i][j][0/1]表示构成i到j的理想队形从左边来或从右边来的最小操作数

状态转移

if(h[i]<h[i+1]){
    dp[i][j][0]+=dp[i+1][j][0];
}
if(h[i]<h[j]){
    dp[i][j][0]+=dp[i+1][j][1];
}
if(h[j]>h[i]){
    dp[i][j][1]+=dp[i][j-1][0];
}
if(h[j]>h[j-1]){
    dp[i][j][1]+=dp[i][j-1][1];
}

标签:状态,min,len,DP,区间,dp
From: https://www.cnblogs.com/hyfly2000/p/18212412/interval-dp-14kti1

相关文章

  • 【知识点】浅入线段树与区间最值问题
    前言:这又是一篇关于数据结构的文章。今天来讲一下线段树和线段树的基本应用。线段树(SegmentTree),是一种非常高效且高级的数据结构,其主要用于区间查询和与区间更新相关的问题,例如进行多次查询区间最大值、最小值、更新区间等操作。区间最值问题引入常见的线段树题型就是区......
  • 状压dp 例题
    终于在洛谷上发布题解了QWQP10447最短Hamilton路径题解分析题目:一张nnn个点的带权无向图,求起点0......
  • C语言---试计算在区间1 到n 的所有整数中,数字x(0 ≤ x ≤ 9)共出现了多少次?
    #include<stdio.h>intmain(){intn,x;scanf("%d%d",&n,&x);intcount=0;for(inti=1;i<=n;i++){intm=i;//从1开始计算while(m)//循环运行的条件{if(m%10==x)//如果m除以10的余数是x的......
  • dp商品缓存
    缓存更新策略缓存更新是redis为了节约内存而设计出来的一个东西,主要是因为内存数据宝贵,当我们向redis插入太多数据,此时就可能会导致缓存中的数据过多,所以redis会对部分数据进行更新,或者把他叫为淘汰更合适。内存淘汰:redis自动进行,当redis内存达到咱们设定的max-memery的时......
  • hmdp-短信验证
    基于Session实现登录流程发送验证码:用户在提交手机号后,会校验手机号是否合法,如果不合法,则要求用户重新输入手机号如果手机号合法,后台此时生成对应的验证码,同时将验证码进行保存,然后再通过短信的方式将验证码发送给用户短信验证码登录、注册:用户将验证码和手机号进行输入,后......
  • 【教程】WordPress资源下载主题 Modown 书面使用教程
    这篇文章介绍了WordPress资源下载主题Modown的书面使用教程。文章包括安装主题、设置主题选项、自定义分类法、菜单、登录页面、小工具等。使用Modown主题可以通过设置首页模板一和使用mocat短代码来显示分类模块。同时还介绍了如何设置标题模块和显示广告。安装将从模板兔......
  • Java并发编程之newFixedThreadPool线程池
    随着计算机硬件性能的不断提升,多核CPU的普及,现代计算机系统的性能越来越强大。在这样的环境下,如何更好地利用计算机系统的性能优势,提高程序的运行效率,是每一个Java开发者需要思考的问题。Java中提供了多线程编程的支持,但是在多线程编程中,线程的创建、启动、调度等都需要耗费一定的......
  • diffusion model(一):DDPM技术小结 (denoising diffusion probabilistic)
    发布日期:2023/05/18主页地址:http://myhz0606.com/article/ddpm1从直觉上理解DDPM在详细推到公式之前,我们先从直觉上理解一下什么是扩散对于常规的生成模型,如GAN,VAE,它直接从噪声数据生成图像,我们不妨记噪声数据为\(z\),其生成的图片为\(x\)对于常规的生成模型:学习一个解码函......
  • dpkg和rpm对比及常用命令
    dpkg(DebianPackage)和rpm(RPMPackageManager)是两种不同的Linux包管理工具,它们各自在特定的Linux发行版中占据核心地位。两者之间对比如下:所属发行版:dpkg主要用于Debian及其衍生系统,如Ubuntu、Knoppix等。而rpm则主要用于RedHat及其衍生系统,如CentOS和Fedora。软件包格式:d......
  • 线段(线性dp)
     题目链接:https://www.luogu.com.cn/problem/P3842思路:f[i][0]表示走完第i行且停在第i行的左端点最少用的步数f[i][1]同理,停在右端点的最少步数。那么转移就很简单了,走完当前行且停到左端点,那么一定是从右端点过来的,那么从上一行左端点转移的话就是f[i][0]=abs(上一行左端......