首页 > 其他分享 >AT_dp

AT_dp

时间:2023-11-30 19:44:50浏览次数:32  
标签:min int namespace long 100005 dp

AT_dp_a Frog 1

设 \(dp_i\) 表示从 \(1\) 跳到 \(n\) 至少需要多少费用,那么 \(i\) 只能从 \(i-1\) 或 \(i-2\) 跳过来,因此得到

\[dp_i=\min\{dp_{i-1}+|a_i-a_{i-1}|,dp_{i-2}+|a_i-a_{i-2}|\} \]

时间复杂度 \(O(n)\)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[100005],dp[100005];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=2;i<=n;i++){
		dp[i]=dp[i-1]+abs(a[i]-a[i-1]);
		if(i>2)dp[i]=min(dp[i],dp[i-2]+abs(a[i]-a[i-2]));
	}
	cout<<dp[n];
	return 0;
}

AT_dp_b Frog 2

看见 \(K\) 非常小,所以可以暴力。

设 \(dp_i\) 表示从 \(1\) 跳到 \(n\) 至少需要多少费用,那么与上题类似

\[dp_i=\min_{j=1}^{min(i-1,k)}dp_{i-j}+|a_i-a_{i-j}| \]

时间复杂度 \(O(NK)\)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[100005],dp[100005],k;
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=2;i<=n;i++){
		dp[i]=LONG_LONG_MAX;
		for(int j=1;j<=min(i-1,k);j++)dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-	j]));
	}
	cout<<dp[n];
	return 0;
}

AT_dp_c Vacation

还是很好想的。设 \(dp_{i,j}\) 表示第 \(i\) 天选第 \(j\) 种事情的最大幸福值,那么

\[dp_{i,0}=\max\{dp_{i-1,1},dp_{i-1,2}\}+a_i \]

\[dp_{i,1}=\max\{dp_{i-1,0},dp_{i-1,2}\}+b_i \]

\[dp_{i,2}=\max\{dp_{i-1,0},dp_{i-1,1}\}+c_i \]

最终答案是 \(\max\{dp_{n,0},dp_{n,1},dp_{n,2}\}\)。

时间复杂度 \(O(n)\)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[100005],b[100005],c[100005],dp[100005][3];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>c[i];
	for(int i=1;i<=n;i++){
		dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i];
		dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i];
		dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i];
	}
	cout<<max({dp[n][0],dp[n][1],dp[n][2]});
	return 0;
}

AT_dp_d Knapsack 1

01背包板子。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,W,dp[100005],v[105],w[105],ans;
signed main(){
	cin>>n>>W;
	for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
	for(int i=1;i<=n;i++)for(int j=W;j>=w[i];j--)dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
	for(int i=0;i<=W;i++)ans=max(ans,dp[i]);
	cout<<ans;
	return 0;
}

AT_dp_e Knapsack 2

注意到 \(\sum{v_i}\le 10^5\),所以我们可以设 \(dp_i\) 表示选择的物品价值总和是 \(i\) 中的花费最小值,然后类似转移一下就行了,答案也很好求。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,W,w[105],v[105],dp[100005];
signed main(){
	cin>>n>>W;
	for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
	memset(dp,0x3f,sizeof dp);
	dp[0]=0;
	for(int i=1;i<=n;i++)for(int j=100000;j>=v[i];j--)dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
	for(int i=100000;i;i--)if(dp[i]<=W){
		cout<<i;
		return 0;
	}
}

AT_dp_f LCS

求两个字符串的最长公共子序列是很简单的,我们只需要想如何输出最长公共子序列就行了。

实际上可以找到

标签:min,int,namespace,long,100005,dp
From: https://www.cnblogs.com/DerrickLo/p/17868106.html

相关文章

  • ThreadPoolExecutor线程池内部处理浅析
    我们知道如果程序中并发的线程数量很多,并且每个线程都是执行一个时间很短的任务就结束时,会因为频繁创建线程而大大降低系统的效率,因此出现了线程池的使用方式,它可以提前创建好线程来执行任务。本文主要通过java的ThreadPoolExecutor来查看线程池的内部处理过程。1ThreadPoolExec......
  • 【动态规划】长链剖分优化树形 dp
    我们在树形dp中经常会遇到这样一个模型:设\(f_{x,i}\)表示节点\(x\)的子树中深度为\(x\)的答案...有递推式:\(f_{x,i}=\sum_{son}f_{son,i-1/i+1}\dots\)。这样直接做是\(\Theta(n^2)\)的,我们考虑去优化这个dp。有一个小优化,就是我们想让\(f_x\)直接继承......
  • docker故障:driver failed programming external connectivity on endpoint
    故障现象Errorresponsefromdaemon:driverfailedprogrammingexternalconnectivityonendpointjenkins(ffdc7c9cda72c575d6b045574d1432b256603a3d986a05da319ab7f3af233755):(iptablesfailed:iptables--wait-tnat-ADOCKER-ptcp-d0/0--dport50000-jDN......
  • USDP2.x 安装
    资源说明USDP的下载内容主要分为如下3种类型:类型序号安装包名称安装包说明放置目录1usdp-01-master-privatization-free-2.0.0.0.tar.gzUSDP主程序与大数据服务资源包/opt/usdp-srv/2httpd-rpms.tar.gz、mirror.tgzUSDP离线yum基础源资源包/data......
  • Vue3 + [email protected] + UploadPictureCard
    <template><a-uploadname="file"v-model:file-list="showFileList"list-type="picture-card":multiple="multiple":max-count="maxCount":before-up......
  • NX二次开发 创建基准平面UF_MODL_create_fixed_dplane
    简介:    NX二次开发创建基准平面UF_MODL_create_fixed_dplane代码:doubledouOriginPoint[3]={0,0,5};doubledouPlaneNormal[3]={0,0,1};tag_ttagPlane=NULL_TAG;UF_MODL_create_fixed_dplane(douOriginPoint,douPlaneNormal,&tagPlane);    m......
  • CF1901E Compressed Tree(树dp)
    Problem题目地址Solution来自fcy大佬的思路记\(f_u\)表示假定以\(u\)为根的子树,在压缩后,(子树内的某一个点(包括\(u\)))可以向外(除\(u\)为根的子树外所以点的集合)连一条边时的最大\(sum\)。换言之,我们把树拆成以\(u\)为根的子树(记作\(Tree_u\))和非\(Tree_u\)部分。而......
  • DP2
    DP2UVA12141LineChart先离散化一波,记位置从小到大第\(i\)个元素离散化后的大小为\(a_i\)。这题最大的难点就在于如何避免计重。如果现在要更新\(i\)位置的dp值,且\(\existsp<q,a_p=a_q\neqa_i\),则贪心地考虑用\(q\)转移,而不是\(p\),因为\(q\)位置结尾包......
  • AtcoderDP1
    AtcoderDP1收录非计数dp题。[ABC227F]TreasureHunting(2323)Problem给你一个\(N\timesM\)的矩阵,你需要从坐标\((1,1)\)走到坐标\((N,M)\)去,每次只能向右或者向下走。坐标\((i,j)\)的价值是\(A_{i,j}\)。我们定义一条路径的价值是,这条路径经过的坐标的前\(K\)......
  • CodeforcesDP1
    CodeforcesDP1CF833BTheBakery(2200)Problem将一个长度为\(n\)的序列\(a\)分为\(k\)段,使得总价值最大。一段区间的价值表示为区间内不同数字的个数。\(n\leq35000,k\leqmin(n,50),1\lea_i\len\)。Solution记\(f_{i,l,j}\)表示考虑前\(i\)个数,划分成\(......