首页 > 代码库 > bzoj1026题解

bzoj1026题解

2024-09-06 16:26:33   217人阅读

【解题思路】

　　数位DP。f[i][j]表示以j结尾的i位数中windy数的个数，转移方程f[i][j]=Σf[i-1][k](|j-k|>1)。

　　基于f数组，我们可以统计出1~n内的windy数个数，记为solve(n)，具体怎么实现我不是很会讲啊QAQ，答案即为solve(B)-solve(A-1)。

　　复杂度O(102lgB)。

【参考代码】

技术分享
 1 #include <cmath> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #define REP(I,start,end) for(int I=(start);I<=(end);I++) 6 #define PER(I,start,end) for(int I=(start);I>=(end);I--) 7 using namespace std; 8 int a,b,s[15],f[15][10]; 9 inline int solve(int n)10 {11     int len=1,result=0;12     s[1]=n%10;13     while(n/=10)14         s[++len]=n%10;15     PER(i,len,1)16     {17         if(len-i>1&&abs(s[i+1]-s[i+2])<2)18             break;19         REP(j,0+(i==len),s[i]+(i==1)-1)20             if(i==len||abs(j-s[i+1])>1)21                 result+=f[i][j];22     }23     REP(i,1,len-1)24         REP(j,1,9)25             result+=f[i][j];26     return result;27 }28 int main()29 {30     memset(f,0,sizeof(f));31     REP(i,0,9)32         f[1][i]=1;33     REP(i,2,10)34         REP(j,0,9)35             REP(k,0,9)36                 f[i][j]+=f[i-1][k]*(abs(j-k)>1);37     scanf("%d%d",&a,&b);38     printf("%d\n",solve(b)-solve(a-1));39     return 0;40 }
View Code

 

bzoj1026题解


联系
我们