首页 > ACM题库 > HDU-杭电 > HDU 4713-Permutation-动态规划-[解题报告]HOJ
2015
09-17

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

Permutation

问题描述 :

A permutation of n elements is a one-to-one function (injection) p: {1,2,…,n} -> {1,2,…,n}. An order of permutation p is the minimal k >= 1, such that for all i=1,2,…,n we have:
p(p(....p(i)...)) = i


That is, p composed with itself k times becomes identity function. For example, the order of the permutation of 3 elements p(1)=3, p(2)=2, p(3)=1 is 2, because p(p(1))=1, p(p(2))=2, p(p(3))=3.
For a given n let us consider permutations of n-elements having the the largest order possible. For example, the maximal order of a permutation of 5 elements is 6. An example of a permutation of 5 elements whose order is 6 is p(1)=4, p(2)=5, p(3)=2, p(4)=1, p(5)=3.
Among all permutations of n elements having the maximal order, we would like to find the earliest one (in a lexycographic order). Being more precise, we say a permutation p of n elements is earlier than a permutation r of n elements, if there is i, such that p(j) = r(j) for all j < i and p(i) < r(i). The earliest permutation of 5 elements having an order 6 is p(1)=2,p(2)=1,p(3)=4,p(4)=5,p(5)=3.

输入:

There is one positive integer t (1 <= t <= 30) in the first line of the standard input. In the following T lines there are positive integers N1, N2, …, Nt, one per line, 1 <= ni <= 10000.

输出:

There is one positive integer t (1 <= t <= 30) in the first line of the standard input. In the following T lines there are positive integers N1, N2, …, Nt, one per line, 1 <= ni <= 10000.

样例输入:

2
5
14

样例输出:

2 1 4 5 3
2 3 1 5 6 7 4 9 10 11 12 13 14 8

#include<cstdlib>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<list>
#include<queue>
#include<vector>
#define tree int o,int l,int r
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define lo o<<1
#define ro o<<1|1
#define ULL unsigned long long
#define LL long long
#define inf 0x7fffffff
#define eps 1e-7
#define N 10001
using namespace std;
int m,n,T,t,x,y,u;
bool vis[N];
int p[N],pn;
vector<int>g[N];
double d[N];
int ans[N];
void init()
{
    for(int i=2; i<N; i++)
    {
        if(!vis[i])
        {
            p[pn++]=i;
            for(int j=i*i; j<N; j+=i)
                vis[j]=1;
        }
    }
    for(int i=0; i<pn; i++)
    {
        for(int j=N-1; j>=p[i]; j--)
        {
            double tp=log2(p[i]);
            for(int k=p[i],num=1; k<=j; k*=p[i],num++)
                if(d[j]<d[j-k]+tp*num)
                {
                    d[j]=d[j-k]+tp*num;
                    g[j]=g[j-k];
                    g[j].push_back(k);
                }
        }
    }
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("ex.in","r",stdin);
#endif
    init();
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        int sum=0,m=0;
        for(int i=0; i<g[n].size(); i++)
        {
            sum+=g[n][i];
            ans[m++]=g[n][i];
        }
        for(int i=sum; i<n; i++)
            ans[m++]=1;
        sort(ans,ans+m);
        
        int f=0,t=1;
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<ans[i]-1; j++)
            {
                if(f)putchar(' ');
                printf("%d",t+j+1);
                f=1;
            }
            if(f)putchar(' ');
            printf("%d",t);
            f=1;
            t+=ans[i];
        }
        puts("");
    }

    return 0;
}

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

参考:http://blog.csdn.net/sunbaofeng2/article/details/11661859