P2657 [SCOI2009]windy数 （数位DP）

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int INF=2e9; int dp[15][15]; int maxNum[15];//每一位数字的最大值 int dfs(int len,int lastVal,bool isMaxed,bool isLead){//lead: 是否有前导零 if(len==0)return 1;//递归边界 if((!isLead)&&(!isMaxed)&&dp[len][lastVal]) return dp[len][lastVal]; int cnt=0; int nowMaxVal=(isMaxed?maxNum[len]:9);//当前位最大值 for(int i=0;i<=nowMaxVal;i++){//枚举当前位数字 if(abs(i-lastVal)<2)continue; int nowNum=i;//当前位数字 bool stillLead=0;//仍然是前导零 if(isLead&&i==0){ nowNum=-INF;//仍然存在前导零 stillLead=1; } cnt+=dfs(len-1,nowNum,(isMaxed)&&(i==nowMaxVal),stillLead); } if(!isLead) dp[len][lastVal]=cnt; return cnt; } int solve(int x){ int nowDigit=0;//当前位数 while(x){//数字分割 maxNum[++nowDigit]=x%10; x/=10; } return dfs(nowDigit,-INF,1,1); } int main(){ int l,r; scanf("%d%d",&l,&r); printf("%d\n",solve(r)-solve(l-1)); return 0; }