一、前置知识
1.DP小知识
D P DP DP 是一种算法思想,用递推方程的方式解决问题。但是使用它要满足如下性质:
- 最优子结构: 子结构优秀,整个就优秀。
- 无后效性:当前决策不会影响后面。
2.DP实现方法
众所周知, D P DP DP 可以使用记忆化搜索实现。模板:
int dp[状态];
int dfs(当前状态){if (满足退出条件) return 退出返回值;if (dp[当前状态]!=-1) return dp[当前状态];int ans=0; 辅助变量进行状态转移return dp[当前状态]=ans;
}memset(dp,-1,sizeof(dp));
二、问题提出
给你一个区间 [ l , r ] [l,r] [l,r] 和一个条件,求区间内满足条件的数的个数。
要求复杂度 O ( l o g 10 n ) O(log_{10}n) O(log10n)。
三、解决问题
我们以一个具体问题入手:数页码。
看如下树形图:
接下来我们可以设计转移:
int dp[20][210];//dp[i][j]表示i位和为j的数字个数
但是如果改一下:
我们会发现,有时数位有限制,所以我们要增加一维 l i m lim lim,表示是否有限制。
强调一下: 有的问题会有 前导零的特殊处理方式,则需要加一位 z e ze ze,表示有没有前导零。
四、蓝题解答
windy数。
可以增加一维 p r e pre pre,表示上一位去什么数。(本题涉及前导零,请谨慎思考)。
代码(附带模板):
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[20][10][2][2],num[20],tot;
//id pre lim
int dfs(int id,int pre,int lim,int ze){//位数,前一位 ,限制,前导零//if (id!=tot&&ze)if (id==0) return 1-ze;if (dp[id][pre][lim][ze]!=-1){return dp[id][pre][lim][ze];}int ans=0,up=(lim?num[id]:9);for (int i=0; i<=up; i++){if (abs(pre-i)>=2||ze){ans+=dfs(id-1,i,lim&&(i==up),ze&&(i==0));}}//cout<<id<<" "<<pre<<" "<<lim<<" "<<ze<<" "<<ans<<"\n";return dp[id][pre][lim][ze]=ans;
}int solve(int x){tot=0; memset(dp,-1,sizeof(dp));while (x) num[++tot]=x%10,x/=10;//cout<<tot<<"\n";return dfs(tot,0,1,1);
}
signed main(){int l,r; cin>>l>>r;cout<<solve(r)-solve(l-1);//cout<<solve(r)<<" "<<solve(l-1);
}
五、特别说明
今天是母亲节,要特别感谢妈妈!
没有她们的大力支持,就没有我们这些 蒟蒻 OIer。