6
19
2016
0

[BZOJ1026] [SCOI2009]windy数

直接数位DP不解释

好吧……记录一下相邻的差,然后搞一搞

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const long long N=15;
 
long long A,B,dp[N][10],a[N];
 
long long Abs(long long x){return x>0?x:-x;}
 
void Pre(){
memset(dp,0,sizeof(dp));
for(long long i=0;i<=9;i++)dp[1][i]=1;
for(long long i=2;i<=10;i++){
    for(long long j=0;j<=9;j++){
        for(long long k=0;k<=9;k++)if(Abs(j-k)>=2)dp[i][j]+=dp[i-1][k];
    }
}
}
 
long long DP(long long x){
if(x==0)return 0;
long long cnt=0,ans=0;
while(x){a[++cnt]=x%10;x/=10;}
for(long long i=1;i<=cnt/2;i++)swap(a[i],a[cnt-i+1]);
for(long long i=1;i<a[1];i++)ans+=dp[cnt][i];
for(long long i=1;i<cnt;i++){
    for(long long j=1;j<=9;j++)ans+=dp[i][j];
}
for(long long i=2;i<=cnt;i++){
    for(long long j=0;j<a[i];j++)if(Abs(j-a[i-1])>=2)ans+=dp[cnt-i+1][j];
    if(Abs(a[i]-a[i-1])<2)break;
}
return ans;
}
 
int main(){
freopen("1026.in","r",stdin);
freopen("1026.out","w",stdout);
scanf("%lld %lld",&A,&B);
Pre();
printf("%lld\n",DP(B+1)-DP(A));
return 0;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 415

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com