专栏文章

DP阶段测

lliu_zheng
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqfag7v
此快照首次捕获于
2025/12/04 03:51
3 个月前
此快照最后确认于
2025/12/04 03:51
3 个月前
查看原文

DP阶段测总结

P1115 最大子段和

此题比较简单 需要注意的点是 ：

题目描述： 选出其中连续且非空的一段使得这段和最大 所以不能跳着找最大字段和 只需要单层循环

代码如下：

CPP
#include<bits/stdc++.h>
using namespace std;
int n,a[200020],b[200020];
int main(){
	int ans=INT_MIN;
   	cin>>n;
   	for(int i=1;i<=n;i++){
       cin>>a[i];
       if(i==1) b[i]=a[i];
       else b[i]=max(a[i],b[i-1]+a[i]);
       ans=max(ans,b[i]);
   	}
   	cout<<ans;
   	return 0;
}

U523265 怪盗基德的滑翔翼

这题其实就是找最长上升子序列或最长下降子序列 y因为题目描述： “初始时，怪盗基德可以在任何一幢建筑的顶端。他可以选择一个方向逃跑，但是不能中途改变方向（因为中森警部会在后面追击）。因为滑翔翼动力装置受损，他只能往下滑行（即：只能从较高的建筑滑翔到较低的建筑） ”基德可以从任意方向所以最长单调的子序列需要判断

代码如下：

CPP
#include<bits/stdc++.h>
using namespace std;
int t;
const int N=100;
int a[N],dp[N];
int n;
int main(){
	cin>>t;
	while(t--){
		cin>>n;
		int ans=1;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			dp[i]=1;
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<i;j++){
				if(a[i]>a[j]){
					dp[i]=max(dp[i],dp[j]+1);
					ans=max(dp[i],ans);
				}
			}
		}
		for(int i=1;i<=n;i++)dp[i]=1;
		for(int i=1;i<=n;i++){
			for(int j=1;j<i;j++){
				if(a[i]<a[j]){
					dp[i]=max(dp[i],dp[j]+1);
                    ans=max(dp[i],ans);
				}
			}
		}
		cout<<ans<<endl;

	}
	
	return 0;
}

P8707 [蓝桥杯 2020 省 AB1] 走方格

这道题基本框架dp 这需要看都dp[i][j]从哪个方向来 题目描述： “只能向右或者向下走 _”所以逆向看就是从上方来或者从左边来；

但是题目有所限制： “注意，如果行号和列数都是偶数，不能走入这一格中” 所以遍历时加个特判判断i和j是否同时为偶数

代码如下：

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m;
int dp[35][35];
int main(){
	cin>>n>>m;
	dp[1][1]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(i==1&&j==1)continue;
			if(i%2==0&&j%2==0)continue;
			dp[i][j]=dp[i][j-1]+dp[i-1][j];
		}
	}
	cout<<dp[n][m];
	return 0;
}

P6208 [USACO06OCT] Cow Pie Treasures G

这道题方向多了些可以斜着走 并且逆向找的时候可能越界特判就行 逆向时j的下标都得-1 所以j==1时会越界continue就行 并且n和m找的时候需要倒着遍历且i不能大于j

代码如下：

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m;
long long dp[105][105],a[105][105];
int t;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	dp[1][1]=a[1][1];
	for(int j=1;j<=m;j++){
		for(int i=1;i<=n;i++){
			if(i==1&&j==1)continue;	
			if(i>j)continue;
			if(i==1){
				dp[i][j]=max(dp[i+1][j-1],dp[i][j-1])+a[i][j];
				continue;
			}
			if(j==1)continue;
			dp[i][j]=max(dp[i+1][j-1],max(dp[i][j-1],dp[i-1][j-1]))+a[i][j];
		}
	}
	cout<<dp[n][m];
	return 0;
}

P7158 「dWoi R1」Password of Shady

n=1时 0<=x<=9 肯定输出9 并且此题需要开long long 不开会爆

状态转移方程：f[i]=f[i−1]×9+g[i−1]

状态转移：g[i]=g[i−1]×9+f[i−1]

代码如下：

CPP
#include<bits/stdc++.h>
using namespace std;
int n;
int t,k;
const int N=1e6+10;
long long dp1[N],dp2[N];
int main(){
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	dp1[1]=1;
	dp2[1]=8;
	for(int i=2;i<=100000;i++){
		dp1[i]=(dp1[i-1]*9+dp2[i-1]*1);
		dp2[i]=(dp2[i-1]*9+dp1[i-1]*1);
		dp1[i]%=998244353;
		dp2[i]%=998244353;
	}
	while(t--){
		cin>>n>>k;
		if(n==1){
			cout<<9<<"\n";
			continue;
		}
		cout<<dp2[n]<<"\n";
		
	}
	
	return 0;
}

P2871 [USACO07DEC] Charm Bracelet S

此题dp背包模板

代码如下：

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=12889;
int dp[N],w[N],d[N];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>d[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=m;j>=w[i];j--){
			dp[j]=max(dp[j],dp[j-w[i]]+d[i]);
		}
	}
	cout<<dp[m];
	return 0;
}

P2677 [USACO07DEC] Bookshelf 2 B

此题也dp模板但求的是背包中奶牛的高度所求却时 “奶牛们叠成的塔最少比书架高的高度” 所以最后用牛的总高度减去放入背包中牛的高度再减去书架高度

代码如下：

CPP
#include<bits/stdc++.h>
using namespace std;
int ans;
int n,b,h[100000];
int w[100000];
int c;
int main(){
	cin>>n>>b;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i];
		ans+=w[i];
	}
	c=ans-b;
	for(int i=1;i<=n;i++)
	{
		for(int j=c;j>=w[i];j--)
		{
			h[j]=max(h[j],h[j-w[i]]+w[i]);
		}
	}
	cout<<ans-h[c]-b;
	return 0;
}

P1510 精卫填海

状态转移：f[j]=max(f[j],f[j-w[i]]+v[i])

此题01背包 判断能否填满即可

代码如下：

CPP
#include<bits/stdc++.h>
using namespace std;
int v,n,c;
const int N=1e4+10;
int k[N],m[N],dp[N];	
int main(){
//	freopen("T8.in","r",stdin);
//	freopen("T8.out","r",stdout);
	cin>>v>>n>>c;
	for(int i=1;i<=n;i++){
		cin>>k[i]>>m[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=c;j>=m[i];j--){
			dp[j]=max(dp[j],dp[j-m[i]]+k[i]);
		}
	}
	for(int i=0;i<=c;i++){
		if(dp[i]>=v){
			cout<<c-i<<endl;
			return 0;
		}
	}
	cout<<"Impossible"<<endl; 
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...