[BZOJ4521][Cqoi2016]手机号码（数位dp）

手机号码（数位dp）"/>

[BZOJ4521][Cqoi2016]手机号码（数位dp）

题目描述

传送门

题解

很久不写数位dp，向学长学习了一种非常高级的写数位dp的方法。
设f(i,j,k,0/1,0/1,0/1,0/1,0/1)表示前i位，第i位放了数字j，连续k个数相同，是否有连续三个数相同，是否有4，是否有8，是否卡下界L，是否卡上界R的方案数。
多维数组看起来巨爽啊。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define LL long longLL L,R,A[20],B[20],f[20][20][20][2][2][2][2][2],ans;int main()
{scanf("%lld%lld",&L,&R);for (int i=11;i>=1;--i){A[i]=L%10,L/=10;B[i]=R%10,R/=10;}for (int i=A[1];i<=B[1];++i)f[1][i][1][0][i==4?1:0][i==8?1:0][i==A[1]?1:0][i==B[1]?1:0]=1;for (int i=1;i<=10;++i)for (int j=0;j<=9;++j)for (int k=1;k<=11;++k)for (int p=0;p<=1;++p)for (int a=0;a<=1;++a)for (int b=0;b<=1;++b)for (int c=0;c<=1;++c)for (int d=0;d<=1;++d)if (f[i][j][k][p][a][b][c][d]){int l,r;if (c&&d) l=A[i+1],r=B[i+1];else if (!c&&!d) l=0,r=9;else if (!c) l=0,r=B[i+1];else l=A[i+1],r=9;for (int t=l;t<=r;++t){int x=(j==t)?k+1:1;f[i+1][t][x][p|(x>=3?1:0)][a|(t==4?1:0)][b|(t==8?1:0)][c&(t==A[i+1]?1:0)][d&(t==B[i+1]?1:0)]+=f[i][j][k][p][a][b][c][d];}}for (int j=0;j<=9;++j)for (int k=1;k<=12;++k)for (int c=0;c<=1;++c)for (int d=0;d<=1;++d)ans+=f[11][j][k][1][0][1][c][d]+f[11][j][k][1][1][0][c][d]+f[11][j][k][1][0][0][c][d];printf("%lld\n",ans);   
}