1026: [SCOI2009]windy数

题解：

　　其实之前年少无知的时候好像A过...表示当时并不知道什么数位DP

　　今天回来深造一发...

　　其实如果对这个算法稍有了解...看到这题的数据范围应该就YY出来了（蒟蒻博主表示很无力）

　　好吧讲做法：

　　这题的DP其实只是在于一开始的预处理：定义f[i][j]表示长度为i且最高位为j的windy数

　　那么转移方程再YY一发：

　　1 for(int i=;i<=;i++)f[][i]=;

　　     for(int i=;i<=;i++)

　　         for(int j=;j<=;j++)

　　             for(int k=;k<=;k++)

　　                 if(abs(j-k)>=)

　　                     f[i][j]+=f[i-][k];

　　之后就是怎么利用这个f数组了，一个常规套路：

　　对于区间[a,b]的答案，如果我们可以求出1~b的答案和1~a-1的答案，那么输出[1~b]-[1~a-1]就是答案了啊。。

　　那么我的做法是用一个getsum函数，求出1~n-1的答案，最后两个区间相减就ok

　　具体看代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #define qread(x) x=read()

 using namespace std;

 inline int read()

 {

     int f=,x=;char ch;

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return f*x;

 }

 int A,B;

 int f[][];//长度为i,最高位为j

 int w[];

 int getsum(int n)//求区间1~n-1的答案

 {

     int len=,ans=;

     memset(w,,sizeof(w));

     while(n!=)

     {

         w[++len]=n%;

         n/=;

     }

     for(int i=;i<len;i++)//比自己至少小一位

         for(int j=;j<=;j++)//枚举开头（所以不能为‘0’）

             ans+=f[i][j];

     for(int i=;i<w[len];i++)//和自己同样位数，但是最高位比自己小

         ans+=f[len][i];

     for(int i=len-;i>=;i--)//最高位一样

     {

         for(int j=;j<w[i];j++)

         {

             if(abs(j-w[i+])>=)

                 ans+=f[i][j];

         }

         if(abs(w[i+]-w[i])<)

             break;

     }

     return ans;

 }

 int main()

 {

        qread(A);qread(B);if(A>B)swap(A,B);

     for(int i=;i<=;i++)f[][i]=;

     for(int i=;i<=;i++)

         for(int j=;j<=;j++)

             for(int k=;k<=;k++)

                 if(abs(j-k)>=)

                     f[i][j]+=f[i-][k];

     int ans1=getsum(B+);

     int ans2=getsum(A);

     //因为getsum求的是1~n-1这个区间的答案，所以我们输出getsum(B+1)-getsum(A);

     printf("%d\n",ans1-ans2);

     return ;

 }

巴特西

bzoj1026: [SCOI2009]windy数（传说你是数位DP）

1026: [SCOI2009]windy数

最新文章

热门文章