P2657 [SCOI2009] windy 数
标签：utc += getch 数位 for span put ace push
数位dp模板题
#include #define inf 2333333333333333
#define N 1000010
#define p(a) putchar(a)
#define For(i,a,b) for(int i=a;i//by war
//2020.7.12
using namespace std;
int l,r;
int f[20][20][3];
vectorint>dim;
void in(int &x){
int y=1;char c=getchar();x=0;
while(c‘0‘||c>‘9‘){if(c==‘-‘)y=-1;c=getchar();}
while(c‘9‘&&c>=‘0‘){ x=(x1)+(x3)+c-‘0‘;c=getchar();}
x*=y;
}
void o(int x){
if(x0){p(‘-‘);x=-x;}
if(x>9)o(x/10);
p(x%10+‘0‘);
}
int dfs(int x,int st,int op){
if(!x) return 1;
if(~f[x][st][op]) return f[x][st][op];
int maxx=op?dim[x]:9,r=0;
For(i,0,maxx){
if(abs(st-i)2) continue;
if(st==11 && i==0) r+=dfs(x-1,11,op&(i==maxx));
else r+=dfs(x-1,i,op&(i==maxx));
}
return f[x][st][op]=r;
}
int deal(int x){
memset(f,-1,sizeof f);
dim.clear();
dim.push_back(2333);
while(x){
dim.push_back(x%10);
x/=10;
}
return dfs(dim.size()-1,11,1);
}
signed main(){
in(l);in(r);
o(deal(r)-deal(l-1));
return 0;
}
P2657 [SCOI2009] windy 数
标签：utc += getch 数位 for span put ace push
原文地址：https://www.cnblogs.com/war1111/p/13292052.html
评论