天天看點

uva 11133 - Eigensequence(dp)

題目大意:給定一個序列a,可以确定一個序列b,要求:

1)b[1]=a[1] 2)a[j?1]<b[j]≤a[j]且b[j]a[j]?a[j?1]為整數,j>1的時候 如果對于每個ai=bi,則稱b序列為Eigensequence序列。 現在給定a1和an,問有多少個Eigensequence序列。

解題思路:dp[i][j]表示第i個數為j的情況有多少種,如果k整除k-j,dp[i+1][k]+=dp[i][j].