程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UESTC 1307 windy數

UESTC 1307 windy數

編輯:C++入門知識

數位dp,dp[i][j][k],

  i表示3類數字:

1類表示windy,0類表示當前所有windy數,0類表示以0開頭的windy但加上前導零就不是windy的數,2類表示除了0類以外的windy

j范圍0~9,表示以j開頭的windy數。

k表示位數
j表示以0~9開頭的數字

 

#include<stdio.h>
#include<string.h>
#define LL long long
int dp[3][11][30];//1表示windy,0表示以0開頭的windy但加上前導零就不是windy的數,2表示除了0類以外的windy
int a[15];
void init()
{
    int i,j,k;
    for(i=0;i<10;i++)dp[1][i][1]=1;
    dp[2][0][1]=1;
    for(i=2;i<12;i++){
        for(j=0;j<10;j++){
            if(j==0){
                for(k=0;k<10;k++){
                    dp[1][j][i]+=dp[1][k][i-1];//以0開頭的,把前面所有的windy都加上去
                    if(k>=2)dp[2][j][i]+=dp[1][k][i-1];//以0開頭的,處理出2類
                }
                continue;
            }
            for(k=0;k<10;k++)
            {
                if(j-k>=2||j-k<=-2){
                   if(k)
                      dp[1][j][i]+=dp[1][k][i-1];//沒有前導零
                   else
                      dp[1][j][i]+=dp[2][k][i-1];//k=0,有前導零,要把0類去掉
                }
            }
        }
    }
}
int solve(int n)
{
    int i,j,k;
    for(i=1;n;i++)
    {
        a[i]=n%10;
        n/=10;
    }
    int len=i,ans=0;
    a[len]=-2;
    for(i=len-1;i>0;i--)
    {
        for(j=0;j<a[i];j++)
        {
          if(j-a[i+1]>=2||j-a[i+1]<=-2)
          {
             if(j==0&&i<len-1){
               ans+=dp[2][j][i];
               continue;
             }
             ans+=dp[1][j][i];
          }
        }
        if((a[i]-a[i+1]<2)&&(a[i]-a[i+1]>-2))break;
    }
    return ans;
}
int main()
{
    init();
    int a,b;
    while(scanf("%d%d",&a,&b)!=-1)
        printf("%d\n",solve(b+1)-solve(a));
    return 0;
}
//123123 3245355

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved