首页 > ACM题库 > HDU-杭电 > HDU 4345-Permutation-动态规划-[解题报告]HOJ
2015
05-23

HDU 4345-Permutation-动态规划-[解题报告]HOJ

Permutation

问题描述 :

There is an arrangement of N numbers and a permutation relation that alter one arrangement into another.
For example, when N equals to 6 the arrangement is 123456 at first. The replacement relation is 312546 (indicate 1->2, 2->3, 3->1, 4->5, 5->4, 6->6, the relation is also an arrangement distinctly).
After the first permutation, the arrangement will be 312546. And then it will be 231456.
In this permutation relation (312546), the arrangement will be altered into the order 312546, 231456, 123546, 312456, 231546 and it will always go back to the beginning, so the length of the loop section of this permutation relation equals to 6.
Your task is to calculate how many kinds of the length of this loop section in any permutation relations.

输入:

Input contains multiple test cases. In each test cases the input only contains one integer indicates N. For all test cases, N<=1000.

输出:

Input contains multiple test cases. In each test cases the input only contains one integer indicates N. For all test cases, N<=1000.

样例输入:

1
2
3
10

样例输出:

1
2
3
16

这题首先是道数学题,用到了置换群的概念,其实是求相加和为N的最小公倍数的种类数,把数学思想抽象出来就成一道dp题了。

 

#include<iostream>
#include<cstdlib>
#include<stdio.h>
#define ll __int64
using namespace std;
const int N=1000;
int prime[N]={0},num=1;
int isprime[N]={1,1};
ll dp[200][1010];
void sushu()
{
    for(int i=2;i<N;i++)
    {
        if(!isprime[i])
        prime[num++]=i;
        for(int j=1;j<num&&i*prime[j]<N;j++)
        {
            isprime[i*prime[j]]=1;
            if(!(i%prime[j]))
            break;
        }
    }
}
int main()
{
    sushu();
    //cout<<num<<endl;
    dp[0][0]=1;
    num--;
    for(int i=1;i<=num;i++)
    {
        for(int j=0;j<=1000;j++)
        dp[i][j]=dp[i-1][j];//前i个质数和为j的不同最小公倍数个数
        int res=prime[i];
        while(res<=1000)
        {
            for(int j=0;j+res<=1000;j++)
            if(dp[i-1][j]) dp[i][j+res]+=dp[i-1][j];
            res*=prime[i];
        }
    }
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        ll ans=0;
        for(int j=1;j<=n;j++)
        ans+=dp[num][j];
        printf("%I64d\n",ans+1);
    }
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/qiqijianglu/article/details/7841664