首页 > 其他分享 >一类特殊的 dp 模型--zhengjun

一类特殊的 dp 模型--zhengjun

时间:2023-07-22 14:44:43浏览次数:38  
标签:插入 -- ll long zhengjun int now dp las

这类问题大概长这样:

求一个排列 \(p_{1\sim n}\),最小(大)化如下值:

\[\sum\limits_{i=1}^{n-1}f(p_i,p_{i+1})\\ f(i,j)= \left\{ \begin{array}{**lr**} g(i)+h(j),i<j\\ h(i)+g(j),i>j \end{array} \right. \]

那么就可以用如下方法 \(O(n^2)\) 解决:

  • 从小到大向序列中插入元素;

  • 记 \(f_{i,j,0/1,0/1}\) 表示,前 \(i\) 个数插入后,分成了 \(j\) 段,首尾分别是否确定 的最小(大)值。

    这里的分段表示后面大的数不能插在一段中间

  • 对 \(i\) 插入位置分类讨论:

    • 插入首位:
      • 在首位新开一个段;
      • 在第一个段最前面插入。
    • 插入末位:
      • 在末位新开一个段;
      • 在最后一个段后面插入。
    • 插入中间:
      • 在任意位置(可以在开头或末位)插入一段

        需要讨论首位末位是否确定判断是否可以插入开头和末位

      • 插入【不是第一个段的段】的开头;
      • 插入【不是最后一个段的段】的末尾;
      • 插入两个段的中间并合并两个段。
  • 然后就做完了,改成计数也是没问题的。

例题

CF704B Ant Man

板题,直接上即可。

甚至帮你决定了要不要插入首位和末位。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5e3+10;
const ll INF=1e18;
int n,st,ed,x[N],a[N],b[N],c[N],d[N];
ll f[N][N];
void chkmin(ll &x,ll y){
	if(x>y)x=y;
}
int main(){
	freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%d%d%d",&n,&st,&ed);
	for(int i=1;i<=n;i++)scanf("%d",&x[i]);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)scanf("%d",&b[i]);
	for(int i=1;i<=n;i++)scanf("%d",&c[i]);
	for(int i=1;i<=n;i++)scanf("%d",&d[i]);
	memset(f,0x3f,sizeof f);
	f[0][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(j>(i>st)+(i>ed))chkmin(f[i][j],f[i-1][j-1]+b[i]-x[i]+d[i]-x[i]);
			if(j>(i>st)&&i!=ed)chkmin(f[i][j],f[i-1][j]+c[i]+b[i]);
			if(j>(i>ed)&&i!=st)chkmin(f[i][j],f[i-1][j]+a[i]+d[i]);
			if(i!=st&&i!=ed)chkmin(f[i][j],f[i-1][j+1]+x[i]+c[i]+x[i]+a[i]);
		}
	}
	cout<<f[n][1]-(b[st]-x[st])-(d[ed]-x[ed]);
	return 0;
}

P2612 [ZJOI2012] 波浪

概率->计数,需要数据分治。

\(K\le 8\) 时可用 long double,否则用 __float128。

由于这题的特殊性,\(g(i)=h(i)\),所以不需要记录首尾分别是否确定。

只要记录首尾确定了几个即可。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int n,m,k;
namespace Solve1{
	const int N=1e2+10,M=N*N,zero=M/2;
	long double f[2][3][N][M];
	void solve(){
		f[0][0][0][zero]=1;
		for(int i=1,now=1,las=0;i<=n;i++,swap(now,las)){
			memset(f[now],0,sizeof f[now]);
			for(int x=0;x<3;x++){
				for(int j=0;j<=n;j++){
					for(int k=0;k<M;k++){
						if(f[las][x][j][k]==0)continue;
						if(j>1&&k+i*2<M)f[now][x][j-1][k+i*2]+=f[las][x][j][k]*(j-1)/i;
						if(k-i*2>=0)f[now][x][j+1][k-i*2]+=f[las][x][j][k]*(j+1-x)/i;
						if(j)f[now][x][j][k]+=f[las][x][j][k]*(j*2-x)/i;
						if(x<2){
							if(j&&k+i<M)f[now][x+1][j][k+i]+=f[las][x][j][k]*(2-x)/i;
							if(k-i>=0)f[now][x+1][j+1][k-i]+=f[las][x][j][k]*(2-x)/i;
						}
					}
				}
			}
		}
		long double ans=0;
		for(int i=m;zero+i<M;i++)ans+=f[n&1][2][1][zero+i];
		printf("%.*Lf",k,ans);
	}
}
namespace Solve2{
	const int N=50+10,M=N*N,zero=M/2;
	__float128 f[2][3][N][M];
	void solve(){
		f[0][0][0][zero]=1;
		for(int i=1,now=1,las=0;i<=n;i++,swap(now,las)){
			memset(f[now],0,sizeof f[now]);
			for(int x=0;x<3;x++){
				for(int j=0;j<=n;j++){
					for(int k=0;k<M;k++){
						if(f[las][x][j][k]==0)continue;
						if(j>1&&k+i*2<M)f[now][x][j-1][k+i*2]+=f[las][x][j][k]*(j-1)/i;
						if(k-i*2>=0)f[now][x][j+1][k-i*2]+=f[las][x][j][k]*(j+1-x)/i;
						if(j)f[now][x][j][k]+=f[las][x][j][k]*(j*2-x)/i;
						if(x<2){
							if(j&&k+i<M)f[now][x+1][j][k+i]+=f[las][x][j][k]*(2-x)/i;
							if(k-i>=0)f[now][x+1][j+1][k-i]+=f[las][x][j][k]*(2-x)/i;
						}
					}
				}
			}
		}
		__float128 ans=0;
		for(int i=m;zero+i<M;i++)ans+=f[n&1][2][1][zero+i];
		int d=(int)ans;
		printf("%d.",d);
		ans-=d;
		for(int d;k--;){
			d=ans*10+(k?0:0.5);
			printf("%d",d);
			ans=ans*10-d;
		}
	}
}
int main(){
	freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n>>m>>k;
	if(k<=8)Solve1::solve();
	else Solve2::solve();
	return 0;
}

标签:插入,--,ll,long,zhengjun,int,now,dp,las
From: https://www.cnblogs.com/A-zjzj/p/17573343.html

相关文章

  • Telegraf&Categraf 主题学习(I)
    基于Telegraf的数据收集系统https://zhuanlan.zhihu.com/p/53376293https://flashcat.cloud/docs/content/flashcat-monitor/categraf/1-introduction/https://n9e.github.io/docs/agent/telegraf/Telegraf监控客户端调研笔记1https://mp.weixin.qq.com/s/JeBa_YOJdsv_QOlCVD......
  • centos装jdk
    1、老男孩linux适合零基础吗?2、centos里如何安装多个版本的jdk?环境变量怎么配,具体点3、实践:在虚拟机中的centos7中安装jdk4、centos7如何找到jdk的安装路径并设置环境变5、如何在centos7中安装jdk1.86、centos如何将jdk更新为18老男孩linux适合零基础吗?1、Linux学习......
  • 用c语言打印日历代码
    1、C语言程序编写日历2、C语言年历显示程序设计3、利用c语言输出某月日历4、C语言编程日历显示C语言程序编写日历1、首先要判断一个年份是闰年还是平年,用一个子程序来做。然后就开始写主程序,首先用scanf得到一个年份。在判断这个年份是平年还是闰年后用printf在CMD中打印......
  • java源码加密代码
    1、java代码想加密怎么处理?2、java加密解密代码3、如何有效防止Java程序源码被人偷窥?4、Java编程实现将文件加密,将源程序补充完整5、用java写个文件加密的代码该怎么写6、java项目如何加密?java代码想加密怎么处理?只给编译后java源码加密的.jar文件java源码加密,不给......
  • Linux 用户和用户组管理
    Linux系统是一个多用户多任务的分时操作系统,任何一个要使用系统资源的用户,都必须首先向系统管理员申请一个账号,然后以这个账号的身份进入系统。用户的账号一方面可以帮助系统管理员对使用系统的用户进行跟踪,并控制他们对系统资源的访问;另一方面也可以帮助用户组织文件,并为用户提......
  • c语言计算整数各位数字之和函数
    1、用C语言写一段,可以计算任意两个输入数的和的程序2、求1到100之和用C语言怎么编程3、c语言编写一个求三个整数和的程序并输出结果。4、用c语言编程如何实现求和的程序代码?用C语言写一段,可以计算任意两个输入数的和的程序1、那么因为阿拉伯数字只有10个所以10进制大......
  • c语言编程三个数的最大值
    1、编写一个c语言程序,输入三个整数,输出它们的最大值2、用C语言求3个数中最大的数?3、c语言编程,求abc三个数的最大值4、如何在C语言编程中求取三个数中的最大值编写一个c语言程序,输入三个整数,输出它们的最大值if(cm)m=c;printf(Maxis%d\n,m);}C语言是一门通用计......
  • 24点游戏编程算法流程图
    1、24点游戏怎么玩?2、24点游戏的规则3、24点算法窍门4、用C语言设计算法完成24点游戏的计算是什么?24点游戏怎么玩?1、拿一副牌,抽去大小王后(也可以把J/Q/K/大小王也拿去),剩下1~10这40张牌(以下用1代替A)。任意抽取4张牌(称为牌组),用加、减、乘、除把牌面上的数算成24。每......
  • html学习day02
    HITML学习Day02一、媒体属性视频属性<video></video>属性:src:资源路径controls:控制条autoplay:自动播放音频属性<audio></audio>属性src:资源路径controls:控制条autoplay:自动播放二、页面结构元素名描述header标记头部区域的内容(用......
  • c语言的一道关于数组的编程题
    1、c语言的一道关于数组的编程题2、编程题:1:定义含有10个元素的数组,并将数组中的元素按逆序从新存放后输...3、c语言编程题:输入10个数存放在一个数组中,输入一个数存入x中,然后找出...c语言的一道关于数组的编程题intcheckNum(intnums[],intlen,intn);//检查n是否存在......