BZOJ1026: [SCOI2009]windy数

• 数位dp。很多小细节。。。
• 代码：
  

   1 #include <bits/stdc++.h>
   2  
   3 using namespace std;
   4 typedef long long ll;
   5 char a[30],b[30];
   6 ll d[30][20]={0};
   7 int la,lb;
   8  
   9 void pre(){
  10     for (int j=0; j<=9; j++) d[1][j]=1;
  11     for (int i=2; i<=lb; i++)
  12         for (int j=0; j<=9; j++)
  13             for (int k=0; k<=9; k++)
  14                 if(abs(j-k)>=2) d[i][j]+=d[i-1][k];
  15 }
  16  
  17 ll solve(char* s,int l){
  18     ll ans=0;
  19     //先算位数小的
  20     for (int i=1; i<l; i++) for (int j=1; j<=9; j++) ans+=d[i][j];
  21     //算位数相等的
  22     for (int i=1; i<s[1]-‘0‘; i++) ans+=d[l][i];
  23     for (int i=2; i<=l; i++) {  //前面都是填的相等的数
  24         for (int j=0; j<(s[i]-‘0‘); j++)   //第i位填j,第i+1位填k
  25             if( abs( j - (s[i-1]-‘0‘) ) >= 2 ) ans+=d[l-i+1][j];
  26         if(abs(s[i]-s[i-1])<2) break;  //不要忘记这个跳出，不合法了都
  27     }
  28     return ans;
  29 }
  30  
  31 bool judge(){  //判断大的那个数是不是
  32     bool flag=true;
  33     for (int i=2; i<=lb; i++) if(abs(b[i]-b[i-1])<=2) { flag=false; break; }
  34     return flag;
  35 }
  36  
  37 int main(){
  38     scanf("%s%s",a+1,b+1);
  39     la=strlen(a+1);
  40     lb=strlen(b+1);
  41     pre();
  42     ll ansa=solve(a,la);
  43     ll ansb=solve(b,lb);
  44     if(judge()) ansb++;
  45     cout<<ansb-ansa<<endl;
  46     return 0;
  47 }

  .....((/- -)/

   

酸菜鱼的 DP动态规划 刷题记录

原文：https://www.cnblogs.com/jiecaoer/p/11397530.html