bzoj 1026: [SCOI2009]windy数 （数位dp）

1026: [SCOI2009]windy数

Time Limit: 1 Sec   Memory Limit: 162 MB
Submit: 6026   Solved: 2690
[ Submit][ Status][ Discuss]

Description

　　windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，
在A和B之间，包括A和B，总共有多少个windy数？

Input

　　包含两个整数，A B。

Output

　　一个整数

Sample Input

【输入样例一】
1 10
【输入样例二】
25 50

Sample Output

【输出样例一】
9
【输出样例二】
20

HINT

【数据规模和约定】

100%的数据，满足 1 <= A <= B <= 2000000000 。

Source

[ Submit][ Status][ Discuss]

题解：数位dp

f[i][j][0/1][0/1][0/1]填到第i位数字为j，是否卡上限，是否卡下线，是否1-（i-1）位前导零的方案总数。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 20
using namespace std;
int n,m,a1[N],b1[N],f[N][N][3][3][3],cnt,ans;
int main()
{
	scanf("%d%d",&n,&m);
	cnt=0;
	while (m)
	{
		a1[++cnt]=m%10;
		m/=10;
	}
	for (int i=cnt;i>=1;i--)
	 b1[cnt-i+1]=a1[i],a1[i]=0;
	int t=0;
	while (n)
	 {
	 	t++;
	 	a1[cnt-t+1]=n%10;
	 	n/=10;
	 }
    for (int i=a1[1];i<=b1[1];i++)
     f[1][i][i==a1[1]?1:0][i==b1[1]?1:0][i==0?1:0]=1;
    for (int i=1;i<cnt;i++)
     for (int j=0;j<=9;j++)
      for (int a=0;a<=1;a++)
       for (int b=0;b<=1;b++)
        for (int c=0;c<=1;c++)
         if (f[i][j][a][b][c])
          {
          	//cout<<i<<" "<<j<<" "<<a<<" "<<b<<" "<<c<<endl;
          	if (a&&b)
          	   {
          	   	  if (c)
          	   	   {
          	   	   	  for (int k=a1[i+1];k<=b1[i+1];k++)
          	   	   	   f[i+1][k][a&(k==a1[i+1]?1:0)][b&(k==b1[i+1]?1:0)][c&(k==0?1:0)]+=f[i][j][a][b][c];
          	   	   	  continue;
				   }
		          for (int k=a1[i+1];k<=b1[i+1];k++)  {
		          	if (k==j||k==j-1||k==j+1) continue;
				    f[i+1][k][a&(k==a1[i+1]?1:0)][b&(k==b1[i+1]?1:0)][c&(k==0?1:0)]+=f[i][j][a][b][c];
				  }
		       }
          	else 
			if (!a&&!b)
			{
			  if (c)
          	   	   {
          	   	   	  for (int k=0;k<=9;k++)
          	   	   	   f[i+1][k][a&(k==a1[i+1]?1:0)][b&(k==b1[i+1]?1:0)][c&(k==0?1:0)]+=f[i][j][a][b][c];
          	   	   	  continue;
				   }
          	  for (int k=0;k<=9;k++)
          	  {
				if (k==j||k==j-1||k==j+1) continue;
				f[i+1][k][a&(k==a1[i+1]?1:0)][b&(k==b1[i+1]?1:0)][c&(k==0?1:0)]+=f[i][j][a][b][c&k];
			  }
			}
			else 
			if (!a)
			{
		      if (c)
          	   	   {
          	   	   	  for (int k=0;k<=b1[i+1];k++)
          	   	   	   f[i+1][k][a&(k==a1[i+1]?1:0)][b&(k==b1[i+1]?1:0)][c&(k==0?1:0)]+=f[i][j][a][b][c];
          	   	   	  continue;
				   }
			  //if (j-2>b1[i+1]) continue;
			  for (int k=0;k<=b1[i+1];k++)
			  {
			    if (k==j||k==j-1||k==j+1) continue;
				f[i+1][k][a&(k==a1[i+1]?1:0)][b&(k==b1[i+1]?1:0)][c&(k==0?1:0)]+=f[i][j][a][b][c]; 
			  }
			}
			else {
			  if (c)
          	   	   {
          	   	   	  for (int k=a1[i+1];k<=9;k++)
          	   	   	   f[i+1][k][a&(k==a1[i+1]?1:0)][b&(k==b1[i+1]?1:0)][c&(k==0?1:0)]+=f[i][j][a][b][c];
          	   	   	  continue;
				   }
			  for (int k=a1[i+1];k<=9;k++)
			  {
			    if (k==j||k==j-1||k==j+1) continue;
				f[i+1][k][a&(k==a1[i+1]?1:0)][b&(k==b1[i+1]?1:0)][c&(k==0?1:0)]+=f[i][j][a][b][c];
			  }
			}
		  }
	for (int i=0;i<=9;i++)
	 for (int a=0;a<=1;a++)
	  for (int b=0;b<=1;b++)
	   for (int c=0;c<=1;c++)
	    ans+=f[cnt][i][a][b][c];
	printf("%d\n",ans);
}