开篇碎碎念
前些日子写期望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链以空格结尾
· 接着考虑转移:
- 对于没有以空格结尾的有三种情况,分别是配对了一整组(配对前也是无空格状态),前一个A链以空格结尾,前一个B链以空格结尾;
- 对于以A链空格作为结尾的也有三种情况,分别是前面在A链以空格结尾,这里贡献是B,另外两种结尾情况的贡献是A(因为算是开始一个新的)
- 对于以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;
}