【ACM练习记录】DP题型详解——2021JNU寒假训练营D2

2023-11-05 06:38
文章标签 dp 详解 记录 练习 训练营 acm 寒假 题型 d2 2021jnu

本文主要是介绍【ACM练习记录】DP题型详解——2021JNU寒假训练营D2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

title : 2021JNU寒假训练营Day2
tags : ACM,练习记录
date : 2021-9-19
author : Linno

logo

题目链接：https://vjudge.net/contest/417488#overview

考察内容：动态规划

题目都比较简单，只要会写板子就行。

A-拦截导弹

思路

在数据量不大的情况下，用dp[i]表示前i个导弹最多能拦截多少个。

枚举i前面j个数，列出转移式 d p [ i ] = m a x ( d p [ i ] , d p [ j ] + 1 ) dp[i]=max(dp[i],dp[j]+1) dp[i]=max(dp[i],dp[j]+1)就能过了。

代码

#include<bits/stdc++.h>
using namespace std;int main(){int k,a[26]={0},dp[26]={0},ans=0;scanf("%d",&k);for(int i=1;i<=k;i++){scanf("%d",&a[i]);}for(int i=k;i>=1;i--){dp[i]=1;for(int j=i+1;j<=k;j++){if(a[j]<=a[i]) dp[i]=max(dp[i],dp[j]+1);}ans=max(ans,dp[i]);}printf("%d",ans);return 0;
}

B-Bone Collector

思路

基础0-1背包板子，不会的话自行百度。

代码

#include<bits/stdc++.h>
using namespace std;int main(){int T;scanf("%d",&T);while(T--){int N,M;long long buy[1001],sale[1001],dp[1001]={0};scanf("%d%d",&N,&M);for(int i=1;i<=N;i++) scanf("%lld",&buy[i]);for(int i=1;i<=N;i++) scanf("%lld",&sale[i]);for(int i=1;i<=N;i++){for(int j=M;j>=sale[i];j--){dp[j]=max(dp[j],dp[j-sale[i]]+buy[i]);}}printf("%lld\n",dp[M]);}
}

C-Super Jumping!Jumping!Jumping!

思路

dp[i]表示前i个数的严格上升子序列最大元素和，转移方程式 i f ( a [ j ] > a [ i ] ) d p [ i ] = m a x ( d p [ i ] , d p [ j ] + a [ i ] ) if(a[j]>a[i]) dp[i]=max(dp[i],dp[j]+a[i]) if(a[j]>a[i])dp[i]=max(dp[i],dp[j]+a[i])

我当时写的代码是 O ( n 2 ) O(n^2) O(n2)的复杂度，最长严格上升子序列问题可以用二分方法加速到 O ( n l o g n ) O(nlogn) O(nlogn)，感兴趣可以去了解。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){int n;scanf("%d",&n);while(n!=0){long long a[1001],dp[1001]={0},ans=0;for(int i=1;i<=n;i++) scanf("%lld",&a[i]);for(int i=n;i>=1;i--){dp[i]=a[i];for(int j=i+1;j<=n;j++){if(a[j]>a[i]) dp[i]=max(dp[i],dp[j]+a[i]);}ans=max(ans,dp[i]);}printf("%d\n",ans);scanf("%d",&n);}return 0;
}

D-dxt数列

思路

这是一道可以用双指针搞定的题目。

代码

#include<stdio.h> 
int main(){int T,n,num=0;scanf("%d",&T);if(T==0) return 0;while(T-num){if(num!=0) printf("\n");int a[100001],b[100001]={0},mx[100001]={0},cnt[100001];for(int i=0;i<n;i++) cnt[i]=0;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a[i]);mx[i]=a[i];}int start=0,end=0,mxx=a[0];for(int i=0;i<n;i++){for(int j=i;j<n;j++){b[i]+=a[j];if(b[i]<0) break;if(b[i]>mx[i]){mx[i]=b[i];cnt[i]=j-i;}}if(mx[i]>mxx){start=i;mxx=mx[i];end=i+cnt[i];}}printf("Case %d:\n",num+1);printf("%d %d %d\n",mxx,start+1,end+1);num++;}return 0;
}

E-免费馅饼

思路

f [ i ] [ j ] f[i][j] f[i][j]表示从i时刻在j位置开始，最多能得到的馅饼数，那么我们对时间倒序枚举，计算每个位置得到的馅饼就可以了。转移表达式如下：
f [ r ] [ l ] = m a x ( f [ r ] [ l ] , f [ r + 1 ] [ l ] + s [ r ] [ l ] ) ; i f ( l + 1 < = 10 ) f [ r ] [ l ] = m a x ( f [ r ] [ l ] , f [ r + 1 ] [ l + 1 ] + s [ r ] [ l ] ) ; i f ( l − 1 > = 0 ) f [ r ] [ l ] = m a x ( f [ r ] [ l ] , f [ r + 1 ] [ l − 1 ] + s [ r ] [ l ] ) ; f[r][l]=max(f[r][l],f[r+1][l]+s[r][l]);\\ if(l+1<=10) f[r][l]=max(f[r][l],f[r+1][l+1]+s[r][l]);\\ if(l-1>=0) f[r][l]=max(f[r][l],f[r+1][l-1]+s[r][l]); f[r][l]=max(f[r][l],f[r+1][l]+s[r][l]);if(l+1<=10)f[r][l]=max(f[r][l],f[r+1][l+1]+s[r][l]);if(l−1>=0)f[r][l]=max(f[r][l],f[r+1][l−1]+s[r][l]);

代码

#include<bits/stdc++.h>
using namespace std;inline void read(int &data){int x=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}data=x;
}int f[100003][13]={0},s[100003][13]={0};int main(){int n,a,b;read(n);while(n!=0){int mt=0;for(int i=0;i<=100001;i++) for(int j=0;j<=10;j++){f[i][j]=0;s[i][j]=0;}for(int i=1;i<=n;i++){read(a);read(b);f[b][a]++;s[b][a]++;if(b>mt) mt=b;}for(int r=mt;r>=0;r--){for(int l=0;l<=10;l++){f[r][l]=max(f[r][l],f[r+1][l]+s[r][l]);if(l+1<=10) f[r][l]=max(f[r][l],f[r+1][l+1]+s[r][l]);if(l-1>=0) f[r][l]=max(f[r][l],f[r+1][l-1]+s[r][l]);}}printf("%d\n",f[0][5]);read(n);}return 0;
}

F-Worm

思路

状态转移： d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + d p [ i − 1 ] [ j + 1 ] ; dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]; dp[i][j]=dp[i−1][j−1]+dp[i−1][j+1];

代码

#include<bits/stdc++.h>
using namespace std;
int n,p,m,t;
long long dp[1005][1005];//dp[i][j]为i时刻到达j树的方案数
int main(){while(scanf("%d%d%d%d",&n,&p,&m,&t)!=EOF){memset(dp,0,sizeof(dp));dp[0][p]=1;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];}} printf("%lld\n",dp[m][t]);} return 0;
}

G-Fruit

思路

这是一个母函数的板子，可以看做是每个物品价值为1，每种物品最多选x~y个，套母函数模板复杂度 O ( n 3 ) O(n^3) O(n3)

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
const int maxn=505;int a[maxn],b[maxn];
int n,m,x[maxn],y[maxn],ans;
//a[i]是目前多项式中i次项的系数
//b[i]是乘当前多项式后的系数 
signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
//	freopen("f.cpp","r",stdin); while(cin>>n>>m){ans=0;memset(a,0,sizeof(a));memset(b,0,sizeof(b));a[0]=1;for(int i=1;i<=n;i++){cin>>x[i]>>y[i];}for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){for(int k=x[i];k+j<=m&&k<=y[i];k++){b[k+j]+=a[j];}}for(int j=0;j<=m;j++){a[j]=b[j];b[j]=0;}}cout<<a[m]<<"\n";}return 0;
}

H-Tickets

思路

递推式比较简单， d p [ i ] = m i n ( d p [ i − 1 ] + a [ i ] , d p [ i − 2 ] + b [ i ] ) ; dp[i]=min(dp[i-1]+a[i],dp[i-2]+b[i]); dp[i]=min(dp[i−1]+a[i],dp[i−2]+b[i]);

感觉主要还是考察输出的细节吧。

代码

#include<bits/stdc++.h>
using namespace std;int n,k,dp[2005],a[2005],b[2005];signed main(){cin>>n;while(n--){cin>>k;for(int i=1;i<=k;i++) cin>>a[i];for(int i=2;i<=k;i++) cin>>b[i];dp[1]=a[1];for(int i=2;i<=k;i++){dp[i]=min(dp[i-1]+a[i],dp[i-2]+b[i]);}int hh=8,mm=0,ss=dp[k];mm+=ss/60;ss%=60;hh+=mm/60;mm%=60;printf("%02d:%02d:%02d ",hh,mm,ss);printf((hh<12)?"am\n":"pm\n");}return 0;
}

I-Treats for the Cow

思路

从外面开始选数，容易想到搜索的做法，但是容易超时。

优化一下思路从里面开始选，逐渐向外扩展到区间[1,n]，用 d p [ 1 ] [ n ] dp[1][n] dp[1][n]表示最终答案。状态转移式： d p [ i ] [ j ] = m a x ( d p [ i + 1 ] [ j ] + v [ i ] ∗ ( n − j + i ) , d p [ i ] [ j − 1 ] + v [ j ] ∗ ( n − j + i ) ) ; dp[i][j]=max(dp[i+1][j]+v[i]*(n-j+i),dp[i][j-1]+v[j]*(n-j+i)); dp[i][j]=max(dp[i+1][j]+v[i]∗(n−j+i),dp[i][j−1]+v[j]∗(n−j+i));

代码

#include<iostream>#define int long longusing namespace std;int n,dp[2005][2005],v[2005],ans=0;//dp[i][j]表示从i到j的最大总分 /*会超时的dfs做法 void dfs(int step,int lf,int rg,int sc){	if(dp[lf][rg]>=sc) return;	dp[lf][rg]=sc;	if(lf+rg==n){		ans=max(ans,sc);		return;	}	dfs(step+1,lf+1,rg,sc+(1+step)*v[lf+1]);	dfs(step+1,lf,rg+1,sc+(1+step)*v[n-rg]);}*/signed main(){	ios::sync_with_stdio(0);	cin.tie(0);cout.tie(0);	cin>>n;	for(int i=1;i<=n;i++){		cin>>v[i];		dp[i][i]=v[i]*n;	}	for(int i=n-1;i>=1;i--){ 		for(int j=i+1;j<=n;j++){			//天数为n-j+i,考虑到[i,j]区间选i还是选j			dp[i][j]=max(dp[i+1][j]+v[i]*(n-j+i),dp[i][j-1]+v[j]*(n-j+i));		}	}	cout<<dp[1][n]<<"\n";	return 0;}

J-Big Event in HDU

思路

我们知道所有物品加起来的总值sum，可以用母函数处理出能够取到的所有价值（系数可忽略不计），如果ans能够被取到，那么sum-ans也可被取到，那么我们只需要让两者最接近sum/2即可。

代码

#include<bits/stdc++.h>#define int long longusing namespace std;const int maxn=300005;int n,ans;int sum,v[maxn],num[maxn];bool a[maxn],b[maxn];signed main(){	ios::sync_with_stdio(0);	cin.tie(0);cout.tie(0);	cin>>n;	while(n>=0){		sum=0;		memset(a,0,sizeof(a));		memset(b,0,sizeof(b));		for(int i=1;i<=n;i++){			cin>>v[i]>>num[i];			sum+=v[i]*num[i];		}		a[0]=1;ans=sum;		for(int i=1;i<=n;i++){			for(int j=0;j<=sum;j++){				for(int k=0;j+k*v[i]<=sum&&k<=num[i];k++){					b[j+k*v[i]]|=a[j];				}			}			for(int j=0;j<=sum;j++){				a[j]=b[j];				b[j]=0;			}		}		for(int i=sum;i>=(sum+1)/2;i--){			if(a[i]) ans=i;		}		cout<<ans<<" "<<sum-ans<<"\n";		cin>>n; 	}	return 0;}

K-yxh的体重和身高

思路

石子合并最简单的形式，区间DP的复杂度 O ( n 3 ) O(n^3) O(n3)可过。

因为有多组输入数据，要注意初始化。

维护一个前缀和用于状态转移。

代码

#include<bits/stdc++.h>#define int long longusing namespace std;const int inf=0x3f3f3f3f;int n,mi[110][110],mx[110][110];//表示i到j的答案 int a[110],sum[110];signed main(){	while(cin>>n){		sum[0]=0;		memset(mx,0,sizeof(mx));		memset(mi,inf,sizeof(mi));		for(int i=1;i<=n;i++){			cin>>a[i];			sum[i]=sum[i-1]+a[i];			mi[i][i]=0;		}		for(int len=2;len<=n;len++){			for(int i=1;i+len-1<=n;i++){				int j=i+len-1;				for(int k=i;k<j;k++){					mx[i][j]=max(mx[i][j],mx[i][k]+mx[k+1][j]+sum[j]-sum[i-1]);					mi[i][j]=min(mi[i][j],mi[i][k]+mi[k+1][j]+sum[j]-sum[i-1]);				}			}		}		cout<<mi[1][n]<<" "<<mx[1][n]<<"\n";	}	return 0;}

L-母牛的故事

思路

递推签到题，参考斐波那契数列。

代码

#include<bits/stdc++.h>using namespace std;int main(){	int n;	long long f[55];	f[1]=1;f[2]=2;f[3]=3;f[4]=4;	for(int i=5;i<=54;i++){		f[i]=f[i-1]+f[i-3];	}	scanf("%d",&n);	while(n!=0){		printf("%lld\n",f[n]); 		scanf("%d",&n);	} 	return 0;}

这篇关于【ACM练习记录】DP题型详解——2021JNU寒假训练营D2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/348081。

相关文章

Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
hdu4826（三维DP）

hdu4826（三维DP）

这是一个百度之星的资格赛第四题 题目链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意：从左上角的点到右上角的点，每个点只能走一遍，走的方向有三个：向上，向下，向右，求最大值。 咋一看像搜索题，先暴搜，TLE,然后剪枝，还是TLE.然后我就改方法，用DP来做，这题和普通dp相比，多个个向上
阅读更多...
hdu1011（背包树形DP）

hdu1011（背包树形DP）

没有完全理解这题， m个人，攻打一个map，map的入口是1，在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下： #include<iostream>#include<algorithm
阅读更多...
OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息，即可快速实现设备配网，是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递，利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力，实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后，即可发送相关配网数据。同时还支持与常规Sof
阅读更多...
hdu4865(概率DP)

hdu4865(概率DP)

题意：已知前一天和今天的天气概率，某天的天气概率和叶子的潮湿程度的概率，n天叶子的湿度，求n天最有可能的天气情况。 思路：概率DP，dp[i][j]表示第i天天气为j的概率，状态转移如下：dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下： #include <stdio.h>#include
阅读更多...
usaco 1.1 Broken Necklace（DP）

usaco 1.1 Broken Necklace（DP）

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于： 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b
阅读更多...
uva 10154 DP 叠乌龟

uva 10154 DP 叠乌龟

题意： 给你几只乌龟，每只乌龟有自身的重量和力量。 每只乌龟的力量可以承受自身体重和在其上的几只乌龟的体重和内。 问最多能叠放几只乌龟。 解析： 先将乌龟按力量从小到大排列。 然后dp的时候从前往后叠，状态转移方程： dp[i][j] = dp[i - 1][j];if (dp[i - 1][j - 1] != inf && dp[i - 1][j - 1] <= t[i]
阅读更多...
uva 10118 dP

uva 10118 dP

题意： 给4列篮子，每次从某一列开始无放回拿蜡烛放入篮子里，并且篮子最多只能放5支蜡烛，数字代表蜡烛的颜色。 当拿出当前颜色的蜡烛在篮子里存在时，猪脚可以把蜡烛带回家。 问最多拿多少只蜡烛。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cs
阅读更多...
uva 10069 DP + 大数加法

uva 10069 DP + 大数加法

代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include <map>#include <cl
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2