蓝桥杯备赛Day12动态规划1基础

动态规划 动态规划基础

动态规划将复杂问题分解成很多重叠的子问题，再通过子问题的解得到整个问题的解 分析步骤: 确定状态:dp[i][j]=val,“到第i个为止，xx为j的方案数/最小代价/最大价值” 状态转移方程: 确定最终状态 要求: (1)最优子结构 (2)无后效性:已经求解的子问题，不会再受到后续决策的影响。 (3)子问题重叠，将子问题的解存储下来 两种思路: (1)按题目

线性DP 数字三角形

学习: (1)将整个大问题分解为一个小问题，就是a[i][j]位置肯定向max(a[i+1][j],a[i+1][j+1])的位置走，所以设置状态dp[i][j]，表示从第i行第j列位置往下走的所有路径的数字和的最大值,可以得到状态转移方程dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1])，然后自底向上遍历，得到最终状态dp[0][0] 代码:

#include <bits/stdc++.h> using namespace std; const int N=105; int n,a[N][N],dp[N][N]; int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n; for(int i=0;i<n;i++){ for(int j=0;j<=i;j++){ cin>>a[i][j]; } } for(int i=n-1;i>-1;i--){ for(int j=0;j<=i;j++){ dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]); //状态转移方程 } } cout<<dp[0][0]; return 0; } 破损的楼梯

学习: (1)状态dp[i]表示走到第i级台阶的方案数，可以有第i-1级台阶或者第i-2级台阶走到，所有得到状态转移方程dp[i]=dp[i-1]+dp[i-2]，得到最终状态dp[n],不能从第n级台阶向下写状态转移方程dp[i]=dp[i+1]+dp[i+2]，因为这样你已经前提假设能走到第n级台阶了，不能走到的情况输出0是错误的 代码:

#include <bits/stdc++.h> using namespace std; const int N=1e5+10; const long long p=1e9+7; int n,m,dp[N]; //状态为从0级台阶走到第i级台阶的方案数 bool mark[N]; //损坏的台阶为true int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=0;i<m;i++){ int t; cin>>t; mark[t]=true; } dp[0]=1; //第1级台阶特殊，只能从0级到达 if(!mark[1]) dp[1]=1; for(int i=2;i<=n;i++){ //是破损台阶，跳过 if(mark[i]) continue; //不是破损台阶，写状态转移方程 //第i级台阶可以由第i-1级台阶或者第i-2级台阶到达 //说明第i级台阶的方案数为第i-1级台阶的方案数加第i-2级台阶的方案数之和 //破损台阶方案数为0 dp[i]=(dp[i-1]+dp[i-2])%p; } cout<<dp[n]; return 0; } 安全序列

学习思路1: (1)此题跟上面不一样，dp[i]表示以i结尾的方案和（这个思想可以学习），比如(1,4)是以4结尾的方案，而(0)就是全都不放的一种方案，所以状态转移方程为 d p [ i ] = ∑ j = 0 i − k − 1 d p [ j ] dp[i]=\sum_{j=0}^{i-k-1} dp[j] dp[i]=j=0∑i−k−1​dp[j] ,其中i-k-1>=0才要这样转移，例如k=2时，以4结尾的方案有(0,4)(1,4)，而不转移的dp都是1，如(0),(1)，再利用前缀和优化 p r e f i x [ i ] = ∑ j = 0 i d p [ j ] prefix[i]=\sum_{j=0}^{i} dp[j] prefix[i]=j=0∑i​dp[j] 代码:

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+10,p=1e9+7; int n,k; ll dp[N],prefix[N]; //dp[i]表示以i结尾(最后一个放1的位置)的方案个数,状态转移方程为dp[i]=dp[0]+...+dp[i-k-1],所以需要前缀和prefix[i]=dp[0]+..+dp[i] int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>k; //以0结尾的方案个数为1(全不放，全为0) ,prefix[-1]无意义，所以要提前初始化 dp[0]=prefix[0]=1; for(int i=1;i<=n;i++){ //当i-k-1>=0时，才有状态转移,反之都是1 if(i-k-1<0) dp[i]=1; else dp[i]=prefix[i-k-1]; //不用减prefix[-1] prefix[i]=(prefix[i-1]+dp[i])%p; } cout<<prefix[n]; //结果不是dp[n],不是以n结尾的方案和，而是dp[0]+...+dp[n] return 0; }

学习思路2: (1)直接用dp[i]来表示共i个空位的方案和，而这一位可以放，也可以不放，方案和=第i位不放的方案+第i位放的方案，第i位不放的方案没有限制条件，就是dp[i-1],而第i位放的方案与i-k-1和0的大小有关。如果i-k-1<0,说明不用考虑隔开k个位置的限制，放就是方案数+1，而如果i-k-1>=0，说明要考虑隔开k个位置的限制，方案数为dp[i-k-1]，分情况得到状态转移方程 代码:

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+10,p=1e9+7; int n,k; ll dp[N]; //dp[i]表示共i个空位的方案和，等于该位置放+不放的方案和 int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>k; dp[0]=1; for(int i=1;i<=n;i++){ //当i-k-1<0时，放就是直接加1，不放就是dp[i-1], if(i-k-1<0) dp[i]=(dp[i-1]+1)%p; //当i-k-1>=0时，放的时候才要考虑dp[i-k-1]，才有意义，不放就是dp[i-1] else dp[i]=(dp[i-1]+dp[i-k-1])%p; } cout<<dp[n]; return 0; } 二维DP

dp数组为二维,描述dp状态的变量不止一个

摆花

学习: (1)状态dp[i][j]表示到第i种花为止(不一定以第i种花结尾，即不一定摆第i种花)，到第j位为止，摆花的方案，因为第i种花可以摆0-a[i]盆，所有dp[i][j]由dp[i-1][j-k],k=0-a[i]这些状态转移而来，相加,图示: ![[摆花.png]]转移方程为: d p [ i ] [ j ] = ∑ k = 0 k = a [ i ] a [ i − 1 ] [ j − k ] dp[i][j]=\sum_{k=0}^{k=a[i]}a[i-1][j-k] dp[i][j]=k=0∑k=a[i]​a[i−1][j−k] 注意初始状态dp[0][0]=1,以及k<=min(j,a[i]),以及不用+=,因为要取模 代码:

#include <bits/stdc++.h> using namespace std; const int N=105,p=1e6+7; int n,m,a[N],dp[N][N]; //dp[i][j]表示到第i种花为止，到第j位为止，摆花的方案数 int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; //初始化dp[0][0]=1,不摆也是一种方案 dp[0][0]=1; //状态转移方程 for(int i=1;i<=n;i++){ //从第1种花开始，到第n种花 for(int j=0;j<=m;j++){ //从第0位开始，到第m位 //状态转移 int t=min(a[i],j); //第i种花最多摆放min(a[i],j]盆 for(int k=0;k<=t;k++){ //第i种花可以摆0-t盆 dp[i][j]=(dp[i][j]+dp[i-1][j-k])%p;//因为要取余，所有不用+= } } } cout<<dp[n][m]; return 0; } 选数异或

学习: (1)这题跟摆花一样，先区分一下子序列和子串的区别: 子序列不一定要求连续，而子串要求连续，两个都要求顺序跟原来一样 dp[i][j]表示到第i个数字为止(不一定以第i个数字结尾，即子序列不一定包括第i个数字),到异或和值为j为止的子序列总数 状态转移方程就是第i-1个数字转移到第i个数字，取第i个数字+不取第i个数字的和: d p [ i ] [ j ] = d p [ i − 1 ] [ j ^ a [ i ] ] + d p [ i − 1 ] [ j ] dp[i][j]=dp[i-1][j\verb|^|a[i]]+dp[i-1][j] dp[i][j]=dp[i−1][j^a[i]]+dp[i−1][j] (2)dp[0][0]=1,因为空子序列的异或和是0，是一个子序列方案 (3)题目说0<=a[i]<63,根据异或性质，异或和不会超过63(63=2^6-1=111111),不管怎么异或都不会超过63，所有能开dp[N][70],j也能从0开始遍历到70 代码:

#include <bits/stdc++.h> using namespace std; const int N=1e5+10,p=998244353; int n,x,a[N],dp[N][70]; //dp[i][j]表示到第i个数字为止(不一定以第i个数字结尾),到值为j为止的子序列个数 int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>x; for(int i=1;i<=n;i++) cin>>a[i]; //dp初始化,定义是空序列的异或和为0 dp[0][0]=1; for(int i=1;i<=n;i++){ for(int j=0;j<70;j++){ //状态转移，包括选第i个数和不选第i个数 dp[i][j]=(dp[i-1][j^a[i]]+dp[i-1][j])%p; } } cout<<dp[n][x]; return 0; } 数字三角形

学习: (1)这题跟线性DP的数字三角形有点不一样，多了一个“向左下走的次数与向右下走的次数相差不能超过 1”的要求，所以自底向上dp状态还要加上一个向右走的次数的维度,dp[i][j][k]表示在(i,j)位置向右走了k次的路径最大和(通过最后状态的k得到结果)，最后的状态要对n分奇偶讨论 代码:

#include <bits/stdc++.h> using namespace std; const int N=105; int n,dp[N][N][55],a[N][N]; //dp[i][j][k]表示在(i,j)位置向右走k次的路径的数字和，相应的向左走的次数为n-i-k int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ cin>>a[i][j]; } } for(int i=n;i>=1;i--){ for(int j=1;j<=i;j++){ //k从0到n-i for(int k=0;k<=n-i;k++){ //k>=1时，才能向右下走 if(k>=1) dp[i][j][k]=a[i][j]+max(dp[i+1][j][k],dp[i+1][j+1][k-1]); //只能向左下走 else dp[i][j][k]=a[i][j]+dp[i+1][j][k]; } } } //共走n-1次，分奇偶讨论,保证向左下走的次数与向右下走的次数相差不能超过 1 //n-1为偶数，n为奇数，都一样 if(n%2) cout<<dp[1][1][(n-1)/2]; //n-1为奇数，n为偶数，取最大 else cout<<max(dp[1][1][(n-1)/2],dp[1][1][n-1-(n-1)/2]); return 0; }

(2) 学习:正因为有了"向左下走的次数与向右下走的次数相差不能超过 1"的要求，所有可以归纳出n为奇数最后走到(n,n/2+1)位置，而n为偶数，最后走到(n,n/2)或者(n,n/2+1)位置(结果位置已知)，所有可以直接自顶向下两个维度得到答案，dp[i][j]表示在(i,j)位置的路径最大和(仔细思考和原来题的区别) 代码:

#include <bits/stdc++.h> using namespace std; const int N=105; int n,dp[N][N],a[N][N]; //dp[i][j]表示在(i,j)位置路径的数字和 int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ cin>>a[i][j]; } } //初始化 dp[1][1]=a[1][1]; for(int i=2;i<=n;i++){ for(int j=1;j<=i;j++){ //从上转移到下 dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]; //是j-1 } } //n为奇数，就一个位置 if(n%2) cout<<dp[n][n/2+1]; else cout<<max(dp[n][n/2],dp[n][n/2+1]); return 0; } LIS(最长上升子序列)

要点: (1)子序列是指按原顺序选出若干不一定连续的元素的子序列，LIS就是该子序列元素是依次递增的，且长度最大。所以,对于固定的数组，虽然LIS序列不一定唯一，但LIS的长度是唯一的 (2)序列元素a[i]，状态dp[i]表示以a[i]结尾的子序列的长度(包括a[i]),初始状态都为1(自己本身),所以状态转移方程就是i>j,if a[i]>a[j],dp[i]=max(dp[i],dp[j]+1),例如:

id: 1 2 3 4 5 6 7 8 a[i]: 1 3 4 2 5 3 7 2 dp[i]: 1 2 3 2 4 3 5 2 从id转移:默认 1 2 1 3 4 5 1

(3)目前只学O(n^2)的LIS，较难的之后再学

蓝桥勇士

学习: (1)典型的LIS问题，套模版即可

#include<bits/stdc++.h> using namespace std; const int N=1e3+10; int n,a[N],dp[N],ans=-1; int main(){ ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; dp[i]=1; } for(int i=2;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(ans,dp[i]); } cout<<ans; return 0; } 合唱队形

学习: (1)结果为左边一个最长子序列，右边一个最长子序列，中间i点截断，所以不妨算dpl和dpr,最终枚举i求得最大值

#include <bits/stdc++.h> using namespace std; const int N=105; int n,a[N],dpl[N],dpr[N];//dpl为从左向右的LIS,dpr为从右向左的LIS,最终枚举i,使得dpl[i]+dp[r]-1最大即可 int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; dpl[i]=1; dpr[i]=1; } //先算dpl for(int i=2;i<=n;i++){ for(int j=1;j<i;j++){ if(a[i]>a[j]) dpl[i]=max(dpl[i],dpl[j]+1); } } //再算dpr for(int i=n-1;i>=1;i--){ for(int j=n;j>i;j--){ if(a[i]>a[j]) dpr[i]=max(dpr[i],dpr[j]+1); } } //最后枚举i，算最终答案 int ans=-1; for(int i=1;i<=n;i++){ ans=max(ans,dpl[i]+dpr[i]-1);//-1是因为i点算了2次 } cout<<n-ans;//ans为合唱队员数量，结果为出列同学数量 return 0; } LCS(最长公共子序列)

学习: (1)求两个序列A，B的最长公共子序列，只有O(n^2)一种解法 (2)状态dp[i][j]为A[1-i],B[1-j](不一定以a[i],b[j]结尾,即公共子序列不一定包括a[i],b[j])时的公共子序列长度,初始值为0,状态转移方程:

if a[i]=b[j] dp[i][j]=dp[i-1][j-1]+1; //相当于把公共元素加入公共子序列，长度加1 else dp[i][j]=max(dp[i-1],dp[j-1]) //相当于向后遍历但不加入公共子序列，长度取最大的

最终状态就是dp[n][m],例如:

A:1 3 4 2 5 B:1 4 3 6 2 dp: i:0 1 2 3 4 5 j: 0 0 0 0 0 0 0 1 0 1 1 1 1 1 2 0 1 1 2 2 2 3 0 1 2 2 2 2 4 0 1 2 2 2 2 5 0 1 2 2 3 3 最长公共子序列: 1 4 2

(3)求完dp数组，再回过来求最长公共子序列元素的方法: 从(n,m)开始回溯,直到跳出边界停止

if a[i]=b[j] 说明从左上角来，回到(i-1,j-1),得到一个最长公共子序列元素 else 说明是从上方或者左侧最大的方法而来 if(dp[i-1][j]>=dp[i][j-1]) 回到(i-1,j)(=默认向上走) else 回到(i,j-1) 最长公共子序列

学习: (1)模版题 代码:

#include <bits/stdc++.h> #include <algorithm> using namespace std; const int N=1e3+10; int n,m,a[N],b[N],dp[N][N]; vector<int> v; //记录最长公共子序列 int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int j=1;j<=m;j++) cin>>b[j]; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ //加入公共子序列 if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1; //不加入 else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } cout<<dp[n][m]<<endl; //打印一个最长公共子序列 int i=n,j=m; //起点 while(i && j){ //是最长公共子序列元素 if(a[i]==b[j]){ v.emplace_back(a[i]); i=i-1,j=j-1; } //不是 else{ if(dp[i-1][j]>=dp[i][j-1]) i=i-1; else j=j-1; } } //反转v,为最长公共子序列元素顺序 reverse(v.begin(),v.end()); for(auto &x:v){ cout<<x<<" "; } return 0; } 真题 接龙数列

学习: (1)这题跟最长上升子序列(LIS)类似，只是判断条件不同罢了，记住dp[i]是以a[i]结尾(不是到a[i]为止不包括a[i]那种)，但是只能拿到50分 (2)cin 从标准输入读取的数据最初都是以 字符序列 的形式存在的，具体是什么类型是自己定义转换得来的，所以这题要获得一个数字的首位和尾位，不用写函数对整数操作，直接把数字当做一个字符串输入，提取首位和尾位即可,不过记得减’0’:

string s; cin>>s; f[i]=s[0]-'0'; e[i]=s[s.size()-1]-'0';

代码:

#include <bits/stdc++.h> using namespace std; const int N=1e5+10; int n,f[N],e[N],dp[N];//f数组记录首位数字，e数组记录末尾数字，dp[i]表示到第i个数字为止(以a[i]为结尾)，最长接龙数列的长度 int main(){ ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++){ string s; cin>>s; f[i]=s[0]-'0'; e[i]=s[s.size()-1]-'0'; dp[i]=1; } int maxn=1; for(int i=2;i<=n;i++){ for(int j=1;j<i;j++){ //状态转移 if(e[j]==f[i]){ dp[i]=max(dp[i],dp[j]+1); } } maxn=max(maxn,dp[i]); } cout<<n-maxn; return 0; }

优化学习: (1)因为这题的条件就是把末位数字等与首位数字的两个数字连接起来，本质上就是一个末位数字的状态转移到另一个末位数字的状态,dp[i]表示以i数字结尾的最长接龙数列，因为数字为0-9，所以dp[10]即可，状态转移方程: dp[b]=max(dp[b],dp[a]+1)(b为第i个数字的末位数字，a为第i个数字的首位数字，即前面某个数字的末位数字)

2023有奖问答

学习: (1)dp填空题，dp[i][j]表示到第i题为止，到分数j为止的方案数，状态转移方程:

dp[i][0]=dp[i-1][0]+dp[i-1][10]+...+dp[i-1][90] dp[i][j]=dp[i-1][j-10] //不用+1，因为表示方案数，状态转移过来这是一种方案,j>=10

(2)根据实际意义初始化dp: dp[1][0]=dp[1][10]=1;//1道题只有0分和10分两种状态 代码:

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll dp[35][101];//dp[i][j]表示到第i题为止，到分数j为止的方案数 int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); //根据实际意义初始化 dp[1][0]=dp[1][10]=1;//1道题只有0分和10分两种状态 ll ans=0; for(int i=2;i<=30;i++){ //dp[i][0]转移 for(int j=0;j<=90;j+=10){ dp[i][0]+=dp[i-1][j]; } //dp[i][j]转移 for(int j=10;j<=100;j+=10){ dp[i][j]=dp[i-1][j-10];//不用+1，因为表示方案数，状态转移过来对于总体来看是一种方案 } } for(int i=1;i<=30;i++){ ans+=dp[i][70]; } cout<<ans; //ans=8335366 return 0; }

填空题暴力dfs代码:

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll ans=0; //x为题目数量，y为分数 void dfs(int x,int y){ //递归中止条件 if(y==100 || x>30) return;//x>30,x可以=30,此时y可能为70 if(y==70) ans++;//只要遇到70就加，当做中途放弃 dfs(x+1,0); dfs(x+1,y+10); } int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); dfs(0,0); cout<<ans; //ans=8335366 return 0; } 2022积木画

学习: (1)这题导致状态转移的原因是添加了一次积木(不一定是1个)，而积木又分I型和L型，所以当前状态可以从添加I型积木前的状态1和添加L型积木前的状态2转移过来(类似于爬楼梯)，当前状态又可能出现两行都有积木、第一行积木比第二行多一个、第二行比第一行多一个三种状态(如何想的过程)，所以定义dp[i][j]表示到第i列为止，j=0,1,2分别表示三种状态，的总方案数,状态转移如下图所示 ![[积木画.png]]代码:

#include <bits/stdc++.h> using namespace std; const int N=1e7+10,p=1000000007; int n,dp[N][3];//dp[i][j]表示到画布第i列为止的方案数,j=0为第一行比第二行多一个,j=1表示两行都一个,j=2表示第二行比第一行多一个 int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n; //先初始化第1列和第2列 dp[1][1]=1,dp[2][0]=dp[2][2]=1,dp[2][1]=2; for(int i=3;i<=n;i++){ //核心状态转移，表示添加I型积木或者L型积木转移过来 //dp[i][0],即第i列第一行比第二行多一个 dp[i][0]=(dp[i-1][2]+dp[i-2][1])%p; //dp[i][2],和dp[i][0]类似，反过来 dp[i][2]=(dp[i-1][0]+dp[i-2][1])%p; //dp[i][1]比较特殊，添加两种类型积木各有两种转移，分类讨论 dp[i][1]=( (dp[i-1][1]+dp[i-2][1])%p + (dp[i-1][0]+dp[i-1][2])%p)%p;//三个取余都不能少，位置也不能不对 } cout<<dp[n][1]; return 0; } 李白打酒加强版

学习: (1)dp问题想好1.状态2.状态转移方程3.什么条件下转移哪些状态(状态的累加)4.最终状态 ![[李白打酒加强版1.png]]![[李白打酒加强版2.png]] 所以一共会有三种状态转移，而利用dp[i][j][k]=(dp[i][j][k]+某种状态方案数)%p可以保证方案数是累加的 (2)本题要求最后一次必遇花，就是求dp[n][m-1][1],同时告诉你遍历到m-1,且酒的量不超过m（因为只能减m*1升),且k>=1，因为最后一次要减1 (3)都从0开始遍历，因为要赋只遇店的和只遇花的值，加上条件判断控制状态转移即可，而不是给0赋一些值（自己考虑不周全），并从1开始遍历(错误方法) 代码:

#include <bits/stdc++.h> using namespace std; const int p=1e9+7; int n,m,dp[105][105][105];//dp[i][j][k]表示到遇店i次为止，遇花j次为止,酒k升为止的方案次数 int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>m; dp[0][0][2]=1; for(int i=0;i<=n;i++){ //必须从0开始，因为i=0或者j=0有很多种情况 for(int j=0;j<=m-1;j++){ //遇花m-1次，最后一次必遇花 for(int k=0;k<=m;k++){ //因为最后要为0，遇花是减1，所以酒的大小不会超过m //遇店 if(i>=1 && k%2==0) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k/2])%p; //遇花(方案累加,加上dp[i][j][k]，如果前面遇店，就等价于加上遇店) if(j>=1 && k>=1) dp[i][j][k]=(dp[i][j][k]+dp[i][j-1][k+1])%p; //k>=1,因为最后一次是遇花，k必须大于等于1 /* //等价于下面的方法 //遇店 if(i>=1 && k%2==0) dp[i][j][k]=dp[i-1][j][k/2]; //遇花 if(j>=1 && k>=1) dp[i][j][k]=dp[i][j-1][k+1]; //k>=1,因为最后一次是遇花，k必须大于等于1 //遇店+遇花 if(i>=1 && k%2==0 && j>=1 && k>=1) dp[i][j][k]=(dp[i-1][j][k/2]+dp[i][j-1][k+1])%p; */ } } } cout<<dp[n][m-1][1];//保证最后一次是花，就是求dp[n][m-1][1] return 0; }

dfs+记忆化+剪枝:

#include<bits/stdc++.h> using namespace std; const int maxn = 100 + 7; const int mod = 1e9 + 7; int dp[maxn][maxn][maxn]; int dfs(int x, int y, int z) // 酒量、遇见店次数、遇见花次数 { if (x < 0 || y < 0 || z < 0) return 0; // 不合法 if (x > z) return 0; // 酒量不可能大于剩余"遇见花的次数" if (z == 1) return y == 0 && x == 1; // 最后一次必须遇到的是花 && 酒量只剩1 if (dp[x][y][z] != -1) return dp[x][y][z]; dp[x][y][z] = (dfs(x * 2, y - 1, z) + dfs(x - 1, y, z - 1)) % mod; return dp[x][y][z]; } int main() { memset(dp, -1, sizeof dp); int n, m; cin >> n >> m; cout << dfs(2, n, m) << endl; return 0; }