DP阶段测
liu_zheng
·
·
个人记录
DP阶段测总结
P1115 最大子段和
此题比较简单 需要注意的点是 ：
题目描述： 选出其中连续且非空的一段使得这段和最大 所以不能跳着找最大字段和 只需要单层循环
代码如下：
#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因为题目描述： “初始时，怪盗基德可以在任何一幢建筑的顶端。他可以选择一个方向逃跑，但是不能中途改变方向（因为中森警部会在后面追击）。因为滑翔翼动力装置受损，他只能往下滑行（即：只能从较高的建筑滑翔到较低的建筑） ”基德可以从任意方向所以最长单调的子序列需要判断
代码如下：
#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是否同时为偶数
代码如下：
#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
代码如下：
#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]
代码如下：
#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背包模板
代码如下：
#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模板但求的是背包中奶牛的高度所求却时 “奶牛们叠成的塔最少比书架高的高度” 所以最后用牛的总高度减去放入背包中牛的高度再减去书架高度
代码如下：
#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背包 判断能否填满即可
代码如下：
#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;
}