dp总结 https://blog.csdn.net/wust_zzwh/article/details/52100392
例1
科协里最近很流行数字游戏。某人命名了一种不降数，这种数字必须满足从左到右各位数字成小于等于的关系，如 123，446。现在大家决定玩一个游戏，指定一个整数闭区间 [a,b]，问这个区间内有多少个不降数。
#include#include #include #include #include #include #include #define ll long longusing namespace std;const int maxn=1000000+10101;inline int read(){ int x=0,f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-'0'; return x*f;}int a,b,dp[20][10],w[30];int find(int x){ int tot=0; while(x){ w[++tot]=x%10; x/=10; } return tot;}int DP(int pos,int statu,bool f){ if(pos==0)return 1; if(!f && dp[pos][statu]!=-1)return dp[pos][statu]; int end=f?w[pos]:9,res=0; for(int i=statu;i<=end;i++){ res+=DP(pos-1,i,f && i==end); } if(!f)dp[pos][statu]=res; return res; }int solve(int x){ int len=find(x); return DP(len,0,1); }int main(){ while(scanf("%d%d",&a,&b)!=EOF){ memset(dp,-1,sizeof(dp)); int len=find(b); printf("%d\n",solve(b)-solve(a-1)); } return 0;}
例2 bzoj1026
Windy定义了一种Windy数。
不含前导零且相邻两个数字之差至少为2的正整数被称为Windy数。Windy想知道，在A和B之间，包括A和B，总共有多少个Windy数？
#include#include #include #include #include #include #include #define ll long longusing namespace std;const int maxn=1000000+10101;inline int read(){ int x=0,f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-'0'; return x*f;}int a,b,dp[20][10],w[30];int find(int x){ int tot=0; while(x){ w[++tot]=x%10; x/=10; } return tot;}int DP(int pos,int statu,bool qian,bool f){ if(pos==0)return 1; if(!f && !qian &&dp[pos][statu]!=-1)return dp[pos][statu]; int end=f?w[pos]:9,res=0; for(int i=0;i<=end;i++){ if(abs(i-statu)<2 && !qian)continue; res+=DP(pos-1,i,i==0 && qian ,f && i==end); } if(!f && !qian)dp[pos][statu]=res; return res;}int solve(int x){ int len=find(x); return DP(len,0,1,1); }int main(){ a=read();b=read(); memset(dp,-1,sizeof(dp)); printf("%d\n",solve(b)-solve(a-1)); return 0;}
例3
由于科协里最近真的很流行数字游戏，某人又命名了一种取模数，这种数字必须满足各位数字之和 mod N为0。现在大家又要玩游戏了，指定一个整数闭区间 [a,b]，问这个区间内有多少个取模数。
#include#include #include #include #include #include #include #define ll long longusing namespace std;const int maxn=1000000+10101;inline int read(){ int x=0,f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-'0'; return x*f;}int a,b,dp[20][100],w[30],n;int find(int x){ int tot=0; while(x){ w[++tot]=x%10; x/=10; } return tot;}int DP(int pos,int sum,bool f){ if(pos==0){ if(sum%n==0)return 1; return 0; } if(!f && dp[pos][sum]!=-1)return dp[pos][sum]; int end=f?w[pos]:9,res=0; for(int i=0;i<=end;i++){ res+=DP(pos-1,(i+sum)%n,f && i==end); } if(!f)dp[pos][sum]=res; return res;}int solve(int x){ int len=find(x); return DP(len,0,1); }int main(){ while(scanf("%d%d%d",&a,&b,&n)!=EOF){ memset(dp,-1,sizeof(dp)); printf("%d\n",solve(b)-solve(a-1)); } return 0;}
例4:
杭州人称那些傻乎乎“粘嗒嗒”的人为 62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。不吉利的数字为所有含有 4 或 62 的号码。例如：62315,73418,88914 都属于不吉利号码。但是，61152虽然含有6和2，但不是 626262 连号，所以不属于不吉利数字之列。你的任务是，对于每次给出的一个牌照区间号，推断出交管局今后又要实际上给多少辆新的士车上牌照了。#include#include #include #include #include #include #include #define ll long longusing namespace std;const int maxn=1000000+10101;inline int read(){ int x=0,f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-'0'; return x*f;}int a,b,dp[20][100],w[30],n;int find(int x){ int tot=0; while(x){ w[++tot]=x%10; x/=10; } return tot;}int DP(int pos,int pre,int sum,bool f){ if(pos==0)return 1; if(!f && dp[pos][sum]!=-1)return dp[pos][sum]; int end=f?w[pos]:9,res=0; for(int i=0;i<=end;i++){ if(i==4)continue; if(i==2 && pre==6)continue; res+=DP(pos-1,i,i,f && i==end); } if(!f)dp[pos][sum]=res; return res;}int solve(int x){ int len=find(x); return DP(len,0,0,1); }int main(){ while(scanf("%d%d",&a,&b)!=EOF){ if(a==b && a==0)break; memset(dp,-1,sizeof(dp)); printf("%d\n",solve(b)-solve(a-1)); } return 0;}
例5：
单身！
依然单身！吉哥依然单身！DS级码农吉哥依然单身！所以，他平生最恨情人节，不管是214还是77，他都讨厌！吉哥观察了214和77这两个数，发现：2+1+4=77+7=7×277=7×11最终，他发现原来这一切归根到底都是因为和7有关！所以，他现在甚至讨厌一切和7有关的数！什么样的数和 7 有关呢？如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关：①：整数中某一位是7；②：整数的每一位加起来的和是7的整数倍；③：这个整数是7的整数倍。现在问题来了：吉哥想知道在一定区间内和7无关的数字的平方和。#include#include #include #include #include #include #include #define LL long long#define mod 1000000007using namespace std;LL T,l,r,sl,a[20],f[20];char ch;struct node{ LL num,s,ps;}dp[20][10][10];LL rd(){ sl=0; ch=getchar(); while(ch<'0'||'9'