把数位dp的简单题目做了一下,今天做一个总结与整理
其实所谓的数位dp做了几道题后发现就是一个模板类型问题,(指的是记忆化搜索强推状态转移就有点difficult了),我的经验下面几点:
1.首先确定上界与限制,就可以使得我们把当前这个数以下的所有数都进行遍历.
2.在过程中我们确定如何保留满足题意的答案,比如说 不要 62,我们需要记录前一位是否为6,如果前一位为6我们标记一下,如果下一位为2,我们就continue掉,使得每次到终点的数,都是符合条件的.
3.最后找如何保留当前的状态,也就是记忆化搜索的重要一步.在这里我的做法是首先不要加记忆化搜索,根据题目给出的例子,测一下结果对不对(如果题目少,自己写几个样例测一下),如果对了,说明这个爆搜是可以的,之后再去找状态关系.现在做的题来看,有一下几种状态.二维:比如说不要 62,如果当前没有限制我们可以随便取,我们这一位的答案,只取决于上一位是不是6,所以我们保留 dp[pos][是否为6]即可.三维:如果不要62的题目意思改为:有多少个62连着 比如说 62062 就要两个62相连,这一种还需要加一维表达当前有多少符合答案,因为 62662 之前有61662, 61662在62662前面优先被搜索所以,他会保留状态,但是此时搜索到61662时 dp[2][1]会保存1这个结果,62662搜到dp[2][1]会直接返回1,但这时应该会有2个62,所以我们需要加一维,如果前面62数相同再返回,这样就不会错了.
4.改变up上限时,限制不会变,具体在下面例题中有一个.
5.注意前导0问题,有时候前导0会使状态多加一维.(原因和其他一样,如果统计0的个数),0 0 0 0会被保留为1,如果1 0 0 1,就不行了所以需要保留此时状态
总结完成,开始例题展示叭.
A - 不要62_____HDU - 2089
题意: m-n中有多少个数没有62,也没有4.
分析:我们保留前一位是否为6,如果当前位为2,就continue掉,当前位为4,也continue ,保证最后数据合法即可.状态总结上分析过了.
#include <bits/stdc++.h>
#define E 2.718
using namespace std;
typedef long long ll;
const ll INF=0x7f7f7f7f;
const int maxn=1e6+8;
const double eps=1e-10;
const ll mod=1000000007;
ll n,m;
ll dp[20][2];
ll a[20];
ll dfs(int pos,int pre,int state,bool limit)
{
ll sum=0;
if(pos<1) return 1;
if(!limit&&dp[pos][state]!=-1) return dp[pos][state];
int up=(limit?a[pos]:9);
for(int i=0;i<=up;i++)
{
if(i==4) continue;
if(pre==6&&i==2) continue;
sum+=dfs(pos-1,i,i==6,i==up&&limit);
}
if(!limit) dp[pos][state]=sum;
return sum;
}
ll solve(ll x)
{
ll cnt=0;
while(x)
{
a[++cnt]=x%10;
x/=10;
}
return dfs(cnt,0,1,true);
}
int main()
{
memset(dp,-1,sizeof(dp));
while(scanf("%lld%lld",&n,&m)&&(n||m))
{
printf("%lld\n",solve(m)-solve(n-1));
}
return 0;
}
B - Bomb_____HDU - 3555
题意:m-n中有多少个包含49的数
分析:求出不包含49的数(同上),相减即可.
#include <bits/stdc++.h>
#define E 2.718
using namespace std;
typedef long long ll;
const ll INF=0x7f7f7f7f;
const int maxn=1e6+8;
const double eps=1e-10;
const ll mod=1000000007;
ll n,m;
ll dp[20][2];
ll a[20];
ll dfs(int pos,int pre,int state,bool limit)
{
ll sum=0;
if(pos<1) return 1;
if(!limit&&dp[pos][state]!=-1) return dp[pos][state];
int up=(limit?a[pos]:9);
for(int i=0;i<=up;i++)
{
if(pre==4&&i==9) continue;
sum+=dfs(pos-1,i,i==4,i==up&&limit);
}
if(!limit) dp[pos][state]=sum;
return sum;
}
ll solve(ll x)
{
ll cnt=0;
while(x)
{
a[++cnt]=x%10;
x/=10;
}
return dfs(cnt,0,1,true);
}
int main()
{
memset(dp,-1,sizeof(dp));
int T;scanf("%d",&T);
while(T--)
{
scanf("%lld",&n);
printf("%lld\n",n-solve(n)+1);
}
return 0;
}
C - How Many Zeroes?_____LightOJ - 1140
题意:询问m-n,所有0的个数
分析:首先需要注意的是前导0,我们加一个lead(bool变量控制即可),然后看一下不是前导0的0出现了几次,搜到底就返回0的个数,然后注意前导0又增加了一维(考虑0000 1001).所以三维:
#include <bits/stdc++.h>
#include <stdio.h>
#define E 2.718
using namespace std;
typedef long long ll;
const ll INF=0x7f7f7f7f;
const int maxn=1e6+8;
const double eps=1e-10;
const ll mod=1000000007;
ll n,m;
ll dp[50][50][20];
ll a[50];
ll dfs(int pos,bool lead,int cot,bool limit)
{
ll sum=0;
if(pos<1)
return lead?1:cot;
if(!limit&&dp[pos][cot][lead]!=-1) return dp[pos][cot][lead];
int up=(limit?a[pos]:9);
for(int i=0;i<=up;i++)
{
if(lead) sum+=dfs(pos-1,i==0,cot,limit&&i==up);
else sum+=dfs(pos-1,lead,cot+(i==0),limit&&i==up);
}
if(!limit) dp[pos][cot][lead]=sum;
return sum;
}
ll solve(ll x)
{
ll cnt=0;
while(x)
{
a[++cnt]=x%10;
x/=10;
}
return dfs(cnt,1,0,1);
}
int main()
{
memset(dp,-1,sizeof(dp));
int T;scanf("%d",&T);
int cas=0;
while(T--)
{
scanf("%lld%lld",&n,&m);
printf("Case %d: %lld\n",++cas,solve(m)-solve(n-1));
}
return 0;
}
D - Fast Bit Calculations_____LightOJ - 1032
题意:问0-n中有多少个二进制相邻位是1的总数,比如7=111 7的贡献就是2,问0-n的总贡献.
分析:首先我们可以知道需要保留前一位是否为1,随后我们需要增加一维保留当前 相邻位有多少了,比如0 1 1 1和1 1 1 1,因为0 1 1 1已经将dp[2][1]保留为11,但是1 1 1 1搜到2应该2,但他直接return 1,所以会出错.所以我们在加一维保留 贡献已经贡献了多少即可:
//#include <bits/stdc++.h>
#include<math.h>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#define E 2.718
using namespace std;
typedef long long ll;
const ll INF=0x7f7f7f7f;
const int maxn=1e6+8;
const double eps=1e-10;
const ll mod=1000000007;
ll n,m,k,b;
ll dp[32][2][50];
ll a[100];
ll dfs(int pos,bool pre,ll res,bool limit)
{
ll sum=0;
if(!pos) return res;
if(!limit&&dp[pos][pre][res]!=-1) return dp[pos][pre][res];
int up=(limit?a[pos]:1);
for(int i=0;i<=up;i++)
sum+=dfs(pos-1,i==1,res+(pre&&i==1),limit&&i==up);
if(!limit) dp[pos][pre][res]=sum;
return sum;
}
ll solve(ll x)
{
ll cnt=0;
while(x)
{
a[++cnt]=x%2;
x/=2;
}
return dfs(cnt,0,0,1);
}
int main()
{
int cas=0;
memset(dp,-1,sizeof(dp));
int T;scanf("%d",&T);
while(T--)
{
scanf("%lld",&n);
printf("Case %d: %lld\n",++cas,solve(n));
}
return 0;
} E - Round Numbers_____POJ - 3252
题意:m-n中有多少数 的二进制满足1的个数>=0的个数.
分析:在过程中保留1和0搜到底就return 1>=0即可,状态保留当前1的个数与0的个数就行.
//#include <bits/stdc++.h>
#include <stdio.h>
#include<string.h>
#define E 2.718
//using namespace std;
typedef long long ll;
const ll INF=0x7f7f7f7f;
const int maxn=1e6+8;
const double eps=1e-10;
const ll mod=1000000007;
ll n,m,k;
ll dp[60][50][50];
ll a[50];
inline ll qpow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a;
b/=2;a=a*a;
}
return ans;
}
ll dfs(int pos,bool lead,ll one,ll zero,bool limit)
{
ll sum=0;
if(pos<1)
{
if(lead) return 0;
return zero>=one?1:0;
}
if(!limit&&dp[pos][one][zero]!=-1) return dp[pos][one][zero];
int up=(limit?a[pos]:1);
for(int i=0;i<=up;i++)
{
if(lead) sum+=dfs(pos-1,i==0,one+(i==1),zero,limit&&i==up);
else sum+=dfs(pos-1,lead,one+(i==1),zero+(i==0),limit&&i==up);
}
if(!limit) dp[pos][one][zero]=sum;
return sum;
}
ll solve(ll x)
{
ll cnt=0;
while(x)
{
a[++cnt]=x%2;
x/=2;
}
return dfs(cnt,1,0,0,1);
}
int main()
{
memset(dp,-1,sizeof(dp));
int T;
int cas=0;
scanf("%lld%lld",&m,&n);
printf("%lld\n",solve(n)-solve(m-1));
return 0;
}
F - Investigation_____LightOJ - 1068
题意:在m-n中位数和可以被k整除,数也可以被k整除的数有多少个
分析:我们可以得到位数最大值就是81 9*9,所以k>=90直接输出0,之后我们就可以保留当前位数与当前深搜到的这个数对k取余等于多少,就可以保留到当前的状态,所以还是三维保留:
#include <bits/stdc++.h>
#include <stdio.h>
#define E 2.718
using namespace std;
typedef long long ll;
const ll INF=0x7f7f7f7f;
const int maxn=1e6+8;
const double eps=1e-10;
const ll mod=1000000007;
ll n,m,k;
ll dp[50][90][90];
ll a[50];
inline ll qpow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a;
b/=2;a=a*a;
}
return ans;
}
ll dfs(int pos,ll s,ll cot,bool limit)
{
ll sum=0;
if(pos<1)
{
return s||cot?0:1;
}
if(!limit&&dp[pos][s][cot]!=-1) return dp[pos][s][cot];
int up=(limit?a[pos]:9);
for(int i=0;i<=up;i++)
{
ll x=(s+i*qpow(10,pos-1))%k;
ll y=(cot+i)%k;
sum+=dfs(pos-1,x,y,limit&&i==up);
}
if(!limit) dp[pos][s][cot]=sum;
return sum;
}
ll solve(ll x)
{
ll cnt=0;
while(x)
{
a[++cnt]=x%10;
x/=10;
}
return dfs(cnt,0,0,1);
}
int main()
{
int T;scanf("%d",&T);
int cas=0;
while(T--)
{
memset(dp,-1,sizeof(dp));
scanf("%lld%lld%lld",&m,&n,&k);
if(k>=90) printf("Case %d: %d\n",++cas,0);
else
printf("Case %d: %lld\n",++cas,solve(n)-solve(m-1));
}
return 0;
}
G - Amount of Degrees_____URAL - 1057
题意:这个题问m-n中有多少个数能够分解成k个 b的整数次幂
分析:这个想开考虑的话意思就是 按b进制拆分之后看1的个数有几个而且要保证其余都是0,既然只有0和1,这意思就是说在二进制的情况下深搜,只不过这题我一直WA的点是,up这个上届由于可能他大于1,但我们只搜到1,所以up可能会变成1,但是这时候应该=a[pos],例如四进制下 302 我们只搜 0 1 所以要搜 0 1 但此时up不应该为1,因为如果为1我们搜到1时表明就有限制了,但现在没有限制.恩就这样~:
//#include <bits/stdc++.h>
#include<math.h>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#define E 2.718
using namespace std;
typedef long long ll;
const ll INF=0x7f7f7f7f;
const int maxn=1e6+8;
const double eps=1e-10;
const ll mod=1000000007;
ll n,m,k,b;
ll dp[50][50];
ll a[100];
ll dfs(int pos,bool lead,ll one,bool limit)
{
ll sum=0;
if(pos<1)
{
if(lead) return 0;
return one==k?1:0;
}
int up=(limit?a[pos]:1);
if(!limit&&dp[pos][one]!=-1) return dp[pos][one];
for(int i=0;i<=up&&i<=1;i++)
{
if(lead) sum+=dfs(pos-1,i==0,one+(i==1),limit&&i==up);
else sum+=dfs(pos-1,lead,one+(i==1),limit&&i==up);
}
if(!limit) dp[pos][one]=sum;
return sum;
}
ll solve(ll x)
{
ll cnt=0;
while(x)
{
a[++cnt]=x%b;
x/=b;
}
return dfs(cnt,1,0,1);
}
int main()
{
int T;
int cas=0; memset(dp,-1,sizeof(dp));
scanf("%lld%lld%lld%lld",&m,&n,&k,&b);
ll y=solve(n);ll x=solve(m-1);
printf("%lld\n",y-x);
return 0;
}
最后说一下,我感觉这过程中的状态保留,只要你感觉对结果有影响你就加一维,应该不会错,而且数位dp的数组空间很少,所以这个维数加个两三维没问题.
京公网安备 11010502036488号