首页 > 其他分享 >【动态规划】线性dp /训练记录/

【动态规划】线性dp /训练记录/

时间:2024-03-10 22:22:37浏览次数:34  
标签:int cin long 空格 MAXN 线性 动态 dp

开篇碎碎念

前些日子写期望dp,但是...cf的那个C可以dp但是没有开出来,于是决定重新开始练dp√(一定是因为题目做的不够多捏,加训!)
是根据这个题单来练哒,指路:【动态规划】普及~省选的dp题
然后边练边整理一下思路什么的)))

基本思路

其实动态规划的本质就是暴力(这也是可以说的吗(遁),考虑好状态的表示(一定要不重不漏)然后推式子。
式子的话一定要保证A更新了之后才更新B,不能说A更新了B之后反过来又影响A
因为一个量更新了之后才会更新另一个量,所以时间复杂度是每个维度的最大值的乘积,而空间限制的话基本上是能开2e5以上的,所以可以通过n的上下限来判断一下具体是几维的表示方式。
或许遇到了一些题目之后开始想着去降维优化一下,但是最初的话一定要大胆升维,不要过于谨慎,要自信!

一些黄绿题

1.守望者的逃离

这个题第一次是在暑假的时候随机到的)))然后...又见面了!

· 有两种运动方式分别是 1.按照17m/s的速度远离;2.消耗10点魔法值在一秒内快速移动60m;
· 根据贪心思想,方法2比方法1省时间,但是在恢复期间匀速运动也有可能到达终点。根据动态规划思想,我用s1表示在i时间内走到的最远距离,然后for循环进行更新,当这个阶段选择魔法比纯走路快的时候就用s2更新s1;

点击查看代码
#include<iostream>
using namespace std;
typedef long long ll;
const int MAXN=3e5+10;
int main(){
	ll M,S,T,t=0,s1=0,s2=0;
	cin>>M>>S>>T;
	for(t=1;t<=T;t++){
		s1+=17;
		if(M>=10){
			M-=10;
			s2+=60;
		}
		else{
			M+=4;
		}
		s1=max(s1,s2);
		if(s1>=S){
			break;
		}
	}
	if(s1<S){
		cout<<"No"<<endl;
		cout<<s1<<endl;
	}
	else{
		cout<<"Yes"<<endl;
		cout<<t<<endl;
	}
	return 0;
}

2. 摆花

· 读题发现有两个限制因素,一个是这一种花摆了几盆,另一个是总共摆了几盆,除此之外还有一个印象因素是花的标号, 所以是三重循环
· 三重循环分别讨论放了前几类花,总共放了多少盆花,和本类花放几盆。发现后面两维的话类型重合所以开一个二维数组 dp[i][j]表示从前i种花选出j盆花进行排列的方案数

点击查看代码
#include<iostream>
#include<algorithm>
using namespace std;
int a[105],dp[105][105];
const int mod=1e6+7;
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			for(int k=0;k<=min(j,a[i]);k++){
				dp[i][j]+=dp[i-1][j-k];
				dp[i][j]%=mod;
			}
		}
	}
	cout<<dp[n][m]<<endl;
	return 0;
}

3. 线段

啊这真的可以说的吗,我一开始想分别讨论每一行的进入下一行的点...我是说...对于每个点讨论一下前一行的进入点...复杂度直接上n^3(好好好

· 总共有n行,每行一个线段,总共n个线段。如果想要总路程最短的话那么一定(除了最后一行之外)每一行的结束都是线段的端点。
· 用dp[i][1/0]表示第i行最终停留在左/右端点所用的最少步数。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e4+10;
#define int long long
typedef long long ll;
ll dp[MAXN][2];
int l[MAXN],r[MAXN];
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>l[i]>>r[i];
	}
	dp[1][0]=r[1]-1+r[1]-l[1];
	dp[1][1]=r[1]-1;
	for(int i=2;i<=n;i++){
		dp[i][0]=min(dp[i-1][0]+abs(l[i-1]-r[i])+(r[i]-l[i]),dp[i-1][1]+abs(r[i-1]-r[i])+(r[i]-l[i]));
		dp[i][1]=min(dp[i-1][0]+abs(l[i-1]-l[i])+(r[i]-l[i]),dp[i-1][1]+abs(r[i-1]-l[i])+(r[i]-l[i]));
	}
	cout<<min(dp[n][0]+n-l[n],dp[n][1]+n-r[n])+n-1<<endl;
}

4. 乌龟棋

· 题目一共给了4种牌+一个棋盘,于是考虑按起点到终点的顺序进行转移或者按照牌的数量进行转移
· 发现前者的话前i格格子的分数最大值与取牌的顺序和方式有关,同时由于需要正好使用完M,所以有可能前面的使用影响到了后面分数的获取,所以不满足无后效性,遂delete
· 所以考虑根据张数构造转移方程,用dp[a1][a2][a3][a4]表示用了a1张1和a2张2、a3张3以及a4张4的最大分数,那么由于一次只能使用一张卡牌,所以对于dp[a1][a2][a3][a4]这一状态来说,会从a1-1,a2-1,a3-1,a4-1四种情况转移过来(**当有部分牌子还没被挑选的话记得continue掉!)

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=45;
int a[355];
int cr[5];
int dp[MAXN][MAXN][MAXN][MAXN];
signed main(){
	int n,m,k;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		cin>>k;
		cr[k]++;
	}
	dp[0][0][0][0]=a[0];
	for(int i1=0;i1<=cr[1];i1++){
		for(int i2=0;i2<=cr[2];i2++){
			for(int i3=0;i3<=cr[3];i3++){
				for(int i4=0;i4<=cr[4];i4++){
					int k=i1+i2*2+i3*3+i4*4;
					if(i4!=0)dp[i1][i2][i3][i4]=max(dp[i1][i2][i3][i4-1]+a[k],dp[i1][i2][i3][i4]);
					if(i3!=0)dp[i1][i2][i3][i4]=max(dp[i1][i2][i3-1][i4]+a[k],dp[i1][i2][i3][i4]);
					if(i2!=0)dp[i1][i2][i3][i4]=max(dp[i1][i2-1][i3][i4]+a[k],dp[i1][i2][i3][i4]);
					if(i1!=0)dp[i1][i2][i3][i4]=max(dp[i1-1][i2][i3][i4]+a[k],dp[i1][i2][i3][i4]);
					// cerr<<k<<' '<<i1<<' '<<i2<<' '<<i3<<' '<<i4<<' '<<dp[i1][i2][i3][i4]<<endl;
				}
			}
		}
	}
	cout<<dp[cr[1]][cr[2]][cr[3]][cr[4]]<<endl;
}

5.找爸爸

看到题目:找呀找呀找朋友,找到一个好朋友,敬个礼握个手,你是我的好朋友~(遁

· 看到一个长度为n一个长度为m,想到之前的最长公共上升子序列,考虑dp表示:用dp[i][j]表示A链前i个和B链前j个进行匹配,但是发现这个题目中还有一个空格的设定,所以考虑设计成三维,用0、1、2分别表示当前没有空格、A链以空格结尾,B链以空格结尾
· 接着考虑转移:

  1. 对于没有以空格结尾的有三种情况,分别是配对了一整组(配对前也是无空格状态),前一个A链以空格结尾,前一个B链以空格结尾;
  2. 对于以A链空格作为结尾的也有三种情况,分别是前面在A链以空格结尾,这里贡献是B,另外两种结尾情况的贡献是A(因为算是开始一个新的)
  3. 对于以B链空格作为结尾的情况与2同理
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=3005;
int dp[MAXN][MAXN][3];
int f[5][5];
int a[MAXN],b[MAXN];
signed main(){
	string s;
	cin>>s;
	int n=s.size();
	for(int i=0;i<n;i++){
		if(s[i]=='A')a[i+1]=1;
		else if(s[i]=='T')a[i+1]=2;
		else if(s[i]=='G')a[i+1]=3;
		else a[i+1]=4;
	}
	cin>>s;
	int m=s.size();
	for(int i=0;i<m;i++){
		if(s[i]=='A')b[i+1]=1;
		else if(s[i]=='T')b[i+1]=2;
		else if(s[i]=='G')b[i+1]=3;
		else b[i+1]=4;
	}
	for(int i=1;i<=4;i++){
		for(int j=1;j<=4;j++){
			cin>>f[i][j];
		}
	}
	int A,B;
	cin>>A>>B;
	for (int i=max(n,m);i;--i) {
        dp[0][i][0] = dp[i][0][0] = dp[0][i][2] = dp[i][0][1] = -(1LL << 60);
        dp[0][i][1] = dp[i][0][2] = -A - B * (i - 1);
    }
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dp[i][j][0]=dp[i-1][j-1][0]+f[a[i]][b[j]];
			dp[i][j][0]=max(dp[i-1][j-1][1]+f[a[i]][b[j]],dp[i][j][0]);
			dp[i][j][0]=max(dp[i-1][j-1][2]+f[a[i]][b[j]],dp[i][j][0]);
			
			dp[i][j][1]=dp[i][j-1][0]-A;
			dp[i][j][1]=max(dp[i][j][1],dp[i][j-1][1]-B);
			dp[i][j][1]=max(dp[i][j][1],dp[i][j-1][2]-A);

			dp[i][j][2]=dp[i-1][j][0]-A;
			dp[i][j][2]=max(dp[i][j][2],dp[i-1][j][2]-B);
			dp[i][j][2]=max(dp[i][j][2],dp[i-1][j][2]-A);

			// cerr<<i<<' '<<j<<' '<<dp[i][j][0]<<' '<<dp[i][j][1]<<' '<<dp[i][j][2]<<endl;
		}
	}
	cout<<max(dp[n][m][0],max(dp[n][m][1],dp[n][m][2]))<<endl;
}

标签:int,cin,long,空格,MAXN,线性,动态,dp
From: https://www.cnblogs.com/muyi-meow/p/18062103

相关文章

  • 动态规划 代码随想录
    step:确定dp数组(dptable)以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组需要重做的题:343(整数拆分) 96(二叉搜索树的种类)简单题:509.斐波那契数   70.爬楼梯   746.使用最小花费爬楼梯注意用step一步步来,注意dp【0】是否有含义。 ......
  • 动态规划 背包问题
    分类:01背包 完全背包01:多个物品,每个只有一个,物品有weight和value。背包载重有限制,问最多能放多少;完全:多个物体,每个有无数个dp[i][j]的含义:在【0,i】这么多物品中,放入载重为j的背包内的最大价值。物品/载重载重0载重1载重2载重3物品0    物品1 ......
  • WordPress:常见问题及解决方案
    解决头像不显示问题默认头像效果:Gavatar的头像在国内不能正常访问,如图:设置:把以下php代码添加到模板函数funtions.php文件中if(!function_exists('get_cravatar_url')){/***把Gravatar头像服务替换为Cravatar*@paramstring$url*@return......
  • 关于Flask中View function mapping is overwriting an existing endpoint function
    关于Flask中Viewfunctionmappingisoverwritinganexistingendpointfunction首次编辑:24/3/10/11:03最后编辑:24/3/10/11:57引子背景本来是在写个人网站,以前的代码中,几乎每个视图函数都有类似于:@app.route("/")defindex(): try: returnsend_file("index.html") e......
  • FFmpeg开发笔记(四)FFmpeg的动态链接库介绍
    FFmpeg不仅提供了ffmpeg、ffplay和ffprobe三个可执行程序,还提供了八个工具库,使得开发者能够调用库里面的函数,从而实现更精准的定制化开发需求。这八个库的名字是avcodec、avdevice、avfilter、avformat、avutil、postproc、swresample、swscale,下面分别对这些库展开介绍。更多详细......
  • 通达信筹码资金动态指标公式源码
    {通达信筹码资金动态指标公式源码}XA_1:=COST(0.1);XA_2:=COST(99.900002);XA_3:=(XA_2-XA_1)/10;资金一:(WINNER(XA_1+XA_3)-WINNER(XA_1))*100;资金二:(WINNER(XA_1+XA_3*2)-WINNER(XA_1+XA_3))*100;资金三:(WINNER(XA_1+XA_3*3)-WINNER(XA_1+XA_3*2))*100;资金四:(WI......
  • 2024 年春节集训 _ 第一课 - 期望类型动态规划
    可能会用到的记号:\([P]=\begin{cases}1&(P成立)\\0&(P不成立)\end{cases}\)期望概率\(\texttt{dp}\)\(\texttt{dp}\)的变形当中最为简单易懂但是又思路又最为清奇。与之相关的难题数不胜数。考场上可以想出正解的都是超级神仙。粗浅的提一句,离散变量,也......
  • 2024 年春节集训 _ 第二课 - 数据结构优化动态规划
    【例题\(1\)】递增子序列\(\color{white}{link}\)考虑\(dp.\)\(dp[i][j]\)表示以元素\(i\)为结尾,长度为\(k\)的方案数。那么显而易见就有一个转移方程:\[dp[i][j]=\sum_{a[k]<a[i],\k<i}dp[k][j-1]\]先抛去第二维度的\(j\),这是可以做一个关于\(a[i]\)值的大......
  • Denoising Diffusion Probabilistic Models去噪扩散模型(DDPM)
    DenoisingDiffusionProbabilisticModels去噪扩散模型(DDPM)2024/2/28论文链接:DenoisingDiffusionProbabilisticModels(neurips.cc)这篇文章对DDPM写个大概,公式推导会放在以后的文章里。一、引言Introduction各类深度生成模型在多种数据模态上展示了高质量的样本。生成......
  • WPF 解决 CommandParameter 参数不更新问题
    参考https://devbox.cn/p/WPFCommandParame_71b81418.html环境软件/系统版本说明WindowsWindows10专业版22H219045.4046MicrosoftVisualStudioMicrosoftVisualStudioCommunity2022(64位)-17.6.5Microsoft.NetSDK8.0.101手动安装Mic......