首页 > 代码库 > BZOJ1026 SCOI2009 Windy数 一般DP
BZOJ1026 SCOI2009 Windy数 一般DP
题意：求[A,B]之间，任意相邻两位差值均大于等于2的数的个数题解：设f[i][j]=第i位为j的合法的数的数量，显然有f[i][j]=f[i-1][k],|k-j|≥2。至于统计答案，我们只要能求1-U之间的合法的数的数量，显然答案就是Ans[B]-Ans[A-1]。至于Ans[i]……因为Ans[10^t]比较好求，所以一位一位统计就好。
#include <cmath>#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;#define ll long longconst int MAXN=10;ll A,B,f[MAXN+2][MAXN+2];ll Calc(ll x){ int N=0,g[MAXN]; ll Ans=0; if(!x) return 0; memset(g,0,sizeof(g)); while(x) g[++N]=x%10,x/=10; for(int i=1;i<g[N];i++) Ans+=f[N][i]; for(int i=N-1;i;i--) for(int j=1;j<=9;j++) Ans+=f[i][j]; for(int i=N-1;i;i--){ for(int j=0;j<g[i];j++) if(abs(g[i+1]-j)>=2) Ans+=f[i][j]; if(abs(g[i+1]-g[i])<2) break; } return Ans;}int main(){ cin >> A >> B; for(int i=0;i<=9;i++) f[1][i]=1; for(int i=2;i<=MAXN;i++) for(int j=0;j<=9;j++) for(int k=0;k<=9;k++) if(abs(j-k)>=2) f[i][j]+=f[i-1][k]; cout << Calc(B+1)-Calc(A) << endl; return 0;}
BZOJ1026 SCOI2009 Windy数 一般DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。