ZOJ 4011 Happy Sequence (DP)

Happy Sequence

题意

找一组数列；要求长度为m，且数列的每一项都是前一项的倍数，且数字不大于n。

思路

这道题用动态规划去做，首先找状态，我们设数组f[i][j]表示以i结尾且长度为j的happy sequence个数。

那么状态方程则为：

f[i][j]=sum（f[k][j-1]），k为i的所有因子

解释一下状态方程：

既然f[i][j]表示以i结尾且长度为j的happy sequence个数，那么在此类数列后面再加个i的倍数（i*k%i==0）也是一个happy sequence，所以以i结尾的长度为j的happy sequence个数为所有的以i的因子结尾的长度为j-1的happy sequence个数之和。

参考代码

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
const int mod=1000000007;
int f[2005][2005];
vector<int>V[2005];
void init()
{
    memset(f,0,sizeof(f));

    for(int i=1; i<=2005; i++)V[i].clear();
    for(int i=1; i<=2005; i++)
    {
        for(int j=1; j<=2005; j++)
        {
            if(j%i==0)
            {
                V[j].push_back(i);
            }
        }
    }
    for(int i=1; i<=2005; i++)f[i][1]=1;
    for(int i=2; i<=2000; i++)
    {
        for(int j=1; j<=2000; j++)
        {
            for(int k=0; k<V[j].size(); k++)
            {
                f[j][i]=(f[j][i]%mod+f[V[j][k]][i-1]%mod)%mod;
            }
            f[j][i]%=mod;
        }
    }
}
int main()
{
    int t;
    init();//直接一次性都算出
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            int n,m;
            scanf("%d%d",&n,&m);
            int sum=0;
            for(int i=1; i<=n; i++)
            {
                sum=(sum+f[i][m])%mod;//将所有以不大于n的数结尾且长度为m的happy sequence个数加起来就是答案了
            }
            printf("%d\n",sum);
        }
    }

}

参考自网络