[BZOJ 1026][SCOI 2009]windy數(數位DP)

[BZOJ 1026][SCOI 2009]windy數(數位DP)

很基礎的數位DP題，很早之前我就嘗試做這題，不過當時我被這題嚇死了，現在回過頭做這題，感覺簡單多了。

做這個題時我想到了POJ一道類似的組合數學的題，同樣是按數位統計，有異曲同工之妙。

題目要求[a,b]區間上的windy數個數，我們可以轉化成求[1,a]上的windy數個數-[1,b-1]上的windy數個數。題目轉化成了求[1,x]上的windy數個數，我們就寫個函數cal(x)。另外我們用w[i][j]表示長度為i的數字，最高位為j(注意j可以為0)所組成的windy數個數。很容易推導出公式w[i][j]=Σw[i-1][k]，0<=k<=9，|k-j|>=2。這個問題處理完後，就是按位統計的問題了。（1）首先我們統計出長度小於x的windy數個數，（2）然後再統計出長度等於x，最高位數字小於x的最高位數字的windy數個數，（3）再從次高位到個位逐位按照類似步驟（2）的方法統計即可。為了避免前導零的情況，最高位統計時不能將w[i][0]算進去。

網上很多人從低位到高位的方法進行統計，太復雜了，還要討論，真的不如從高位到低位統計來得方便，囧。

#include 
#include 
#include 
#include 
#include 

#define INF 0x3f3f3f3f

using namespace std;

typedef long long int LL;

int primes[]={0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29}; //質數打表

LL n,ans,cnt; //cnt=約數個數最大值,ans=約數個數取最大值時的最小的數字

void DFS(LL num,LL maxP,int now,int nowcnt) //num=當前乘積得到的數，maxp=下一個質數最大的冪，now=當前狀態下使用的質數下標，nowcnt=當前數約數個數
{
    if(nowcnt>cnt||nowcnt==cnt&&num10) return; //取的質數個數太多了，已經超出了n的范圍，不必繼續搜索了
    LL nownum=num;
    for(int i=1;i<=maxP;i++) //枚舉下一個質因數的冪
    {
        nownum*=(LL)primes[now];
        if(nownum>n) return;
        DFS(nownum,i,now+1,nowcnt*(i+1));
    }
}

int main()
{
    scanf(%lld,&n);
    ans=1,cnt=1;
    DFS(1,INF,1,1);
    printf(%lld
,ans);
    return 0;
}