首页 > 代码库 > 【bzoj1026】 SCOI2009—windy数
【bzoj1026】 SCOI2009—windy数
http://www.lydsy.com/JudgeOnline/problem.php?id=1026 (题目链接)
题意
在区间${[A,B]}$有多少个数相邻两个数位上的数之差至少为2。
Solution
数位dp,右转题解:LCF
其中${f[i][0]}$,表示的是第${i}$位为${0}$的方案数,并不是不取${i}$位。
细节
LL
代码
// bzoj1026#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#include<ctime>#define LL long long#define inf (1ll<<30)#define MOD 1000000007#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;LL f[20][10],g[20],ans;int n,a[2],t[20];LL solve(int p) { memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); for (n=0;a[p];a[p]/=10) t[++n]=a[p]%10; for (int i=0;i<10;i++) f[1][i]=1; for (int i=2;i<=n;i++) for (int j=0;j<10;j++) for (int k=0;k<10;k++) if (abs(j-k)>1) f[i][j]+=f[i-1][k]; g[1]=1; for (int i=2;i<=n;i++) { for (int j=0;j<t[i-1];j++) if (abs(t[i]-j)>=2) g[i]+=f[i-1][j]; if (abs(t[i]-t[i-1])>1) g[i]+=g[i-1]; } LL res=0; for (int i=1;i<n;i++) for (int j=1;j<10;j++) res+=f[i][j]; for (int i=1;i<t[n];i++) res+=f[n][i]; return res+g[n];}int main() { scanf("%d%d",&a[0],&a[1]);a[0]--; ans-=solve(0); ans+=solve(1); printf("%lld",ans); return 0;}
【bzoj1026】 SCOI2009—windy数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。