首页 > 代码库 > 数位DP小小结
数位DP小小结
FZOJ Problem 2113 Jason的特殊爱好
题意：x~y数字里面有多少个 1
思路:我们算法课实验题的简化版，当时我用了很麻烦的一个DP=_=
刚刚学到了很棒的姿势，记忆化DP！！
dfs(int pos ,bool end1) ;
end1==false 返回pos位后面（包含pos）任意组合有多少个 1 ；
end1==true 返回上一位是结尾，Pos以后的位受到限制组合有多少个 1 ；
大概是这样，如果数字是 4987 现在计算到 8 这个数字，end1==true，说明是49XX
XX的取值是0-87；
如果计算到当前位，如果是这位是1 ，如果没有限制，那么答案就是加上10^pos个
如果有限制，那么答案就是加上nn%(10^pos)+1 个，
如果不是结尾(也就是没有限制的)，我们可以dp[pos]保存计算过的结果。
include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<set>#include<stack>#include<map>#include<ctime>#include<bitset>#define LL long long#define ll long long#define INF 0x3f3f3f3f#define maxn 50010#define eps 1e-6#define mod 1000000007using namespace std;LL dp[30] ,nn ;int bit[30] ;LL get1(int pos){ LL tt=1; for(int i=0;i<pos;i++) tt *= 10; return nn%tt;}LL get2(int pos){ LL tt=1; for(int i=0;i<pos;i++) tt *= 10; return tt;}LL dfs(int pos ,bool end1){ if(pos==-1) { return 0; } if(!end1&&dp[pos] != -1) { return dp[pos]; } int e ,ee ; LL ans=0; if(end1) e = bit[pos] ; else e = 9 ; for(int i = 0 ; i <= e ;i++) { if(i==1){ if(i==e)ans += get1(pos)+1; else ans += get2(pos) ; } ans += dfs(pos-1,(end1&&i==e)) ; } if(!end1) { dp[pos] = ans; } return ans;}LL getans(LL n ){ nn=n; int len=0; if(n<=0) return 0 ; while(n) { bit[len++] = n%10 ; n /= 10 ; } LL ans=0; ans = dfs(len-1,1) ; return ans;}int main(){ int i , j , m ,k ,T ; LL x,y ; memset(dp,-1,sizeof(dp)) ; // cout << getans(20)<<endl; while(cin >> x >> y) { y=getans(y) ; x=getans(x-1); cout << y-x<< endl; } return 0 ;}
hdu 3555 Bomb
题意：x~y数字里面有多少个49
思路：和上面做法差不多，只是多了一个状态
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<set>#include<stack>#include<map>#include<ctime>#include<bitset>#define LL long long#define ll long long#define INF 0x3f3f3f3f#define maxn 50010#define eps 1e-6#define mod 1000000007using namespace std;LL dp[30][20] ,nn ;int bit[30] ;LL dfs(int pos ,int num ,bool end1){ if(pos==-1) { return num==2 ; } if(!end1&&dp[pos][num] != -1) { return dp[pos][num]; } int e,ee; LL ans=0; if(end1) e = bit[pos] ; else e = 9 ; for(int i = 0 ; i <= e ;i++) { if(num==1&&i==9) { ee=2; } else if(num==0&&i==4) { ee=1; } else if(num==1&&i != 4) { ee=0; } else ee=num ; ans += dfs(pos-1,ee,(end1&&i==e)) ; } if(!end1) { dp[pos][num] = ans; } return ans;}LL getans(LL n ){ nn=n; int len=0; if(n<=0) return 0 ; while(n) { bit[len++] = n%10 ; n /= 10 ; } LL ans=0; ans = dfs(len-1,0,1) ; return ans;}int main(){ int i , j , m ,k ,T ; LL x,y ; memset(dp,-1,sizeof(dp)) ; // cout << getans(20)<<endl; cin >> T ; while(cin >> y) { y=getans(y) ; cout << y<< endl; } return 0 ;}
hdu 3709 Balanced Number
题意：x-y有多少个是平衡的，平衡的定义是，找一个支点，使得两边的重量一样
思路: 还是和上面的姿势一样，只是状态多了一些~~~
对于 dfs(int pos ,int v,int val,bool end1)
if(end1==false)表示当前计算到第pos位，选的支点为v，前面比后面的重val，后面pos位任意组合
返回的数字数目。
if(end1==true)也就是有限制了
include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<set>#include<stack>#include<map>#include<ctime>#include<bitset>#define LL long long#define ll long long#define INF 0x3f3f3f3f#define maxn 50010#define eps 1e-6#define mod 1000000007using namespace std;LL dp[20][20][2000] ;int bit[30] ;LL dfs(int pos ,int v,int val,bool end1){ if(pos==-1) { return (val==0) ; } if(!end1&&dp[pos][v][val] != -1) { return dp[pos][v][val] ; } if(val<0) return 0 ; int e ,ee ; LL ans=0; if(end1) e = bit[pos] ; else e = 9 ; for(int i = 0 ; i <= e ;i++) { ee = val+(pos-v)*i ; ans += dfs(pos-1,v,ee,(end1&&i==e)) ; } if(!end1) { dp[pos][v][val] = ans; } return ans;}LL getans(LL n ){ int len=0; if(n<0) return 0 ; while(n) { bit[len++] = n%10 ; n /= 10 ; } LL ans=0; for( int i = 0 ; i <len ;i++) { ans += dfs(len-1,i,0,1) ; } return ans-(len-1) ;}int main(){ int i , j , m ,k ,T ; LL x,y ; memset(dp,-1,sizeof(dp)) ; cin >> T ; while(T--) { cin >> x >> y ; y=getans(y) ; x=getans(x-1); cout << y-x<< endl; } return 0 ;}
数位DP小小结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。