poj 3590(dp 置换)

题目的意思是对于序列1,2,...,n。要你给出一种字典序最小的置换使得经过X次后变成最初状态，且要求最小的X最大。

通过理解置换的性质，问题可以等价于求x1,x2,..,xn 使得x1+x2+...+xk=n,且GLM(x1,x2,...,xn)最大。

这个就用dp来做，首先求出100内的所有素数记录为prime[1] 到 prime[25]。

状态：dp[i][j] 表示花费了i，且已经使用prime[1] 到 prime[j]，的最大值。

转移方程：因为要求最大值，单纯的用素数的积并不能得到最大值，最大值得形式是prime[1]^s1*prime[2]^s2*...*prime[25]^s25

for(int i=;i<=cnt;i++)

        {

            long long tmp[];

            for(int j=;j<=n;j++)

                tmp[j]=dp[j];

            for(int k=;mypow(saveprime[i],k)<=n;k++)

            {

                long long tmpnum=mypow(saveprime[i],k);

                for(int j=tmpnum;j<=n;j++)

                {

                    dp[j]=max(tmp[j-tmpnum]*tmpnum,dp[j]);

                }

            }

        }

The shuffle Problem

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 1882		Accepted: 626

Description

Any case of shuffling of n cards can be described with a permutation of 1 to n. Thus there are totally n! cases of shuffling. Now suppose there are 5 cards, and a case of shuffle is <5, 3, 2, 1, 4>, then the shuffle will be:

Before shuffling：1, 2, 3, 4, 5
The 1st shuffle：5, 3, 2, 1, 4
The 2nd shuffle：4, 2, 3, 5, 1
The 3rd shuffle：1, 3, 2, 4, 5
The 4th shuffle：5, 2, 3, 1, 4
The 5th shuffle：4, 3, 2, 5, 1
The 6th shuffle：1, 2, 3, 4, 5(the same as it is in the beginning)

You'll find that after six shuffles, the cards' order returns the beginning. In fact, there is always a number m for any case of shuffling that the cards' order returns the beginning after m shuffles. Now your task is to find the shuffle with the largest m. If there is not only one, sort out the one with the smallest order.

Input

The first line of the input is an integer T which indicates the number of test cases. Each test case occupies a line, contains an integer n (1 ≤ n ≤ 100).

Output

Each test case takes a line, with an integer m in the head, following the case of shuffling.
　

Sample Input

Sample Output

1 1

6 2 1 4 5 3

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <stdlib.h>

#include <algorithm>

#include <iostream>

using namespace std;

int saveprime[];

long long dp[];

int saveans[];

int mypow(int x,int y)

{

    int sum=;

    for(int i=;i<=y;i++)

        sum*=x;

    return sum;

}

int main()

{

    int cnt=;

    for(int i=;i<=;i++)

    {

        int flag=;

        for(int j=;j<i;j++)

        {

            if(i%j==)

            {

                flag=;

                break;

            }

        }

        if(flag==)

        {

            saveprime[++cnt]=i;

        }

    }

    int T;

    cin>>T;

    while(T--)

    {

        int n;

        cin>>n;

        for(int i=;i<=n;i++)

            dp[i]=;

        for(int i=;i<=cnt;i++)

        {

            long long tmp[];

            for(int j=;j<=n;j++)

                tmp[j]=dp[j];

            for(int k=;mypow(saveprime[i],k)<=n;k++)

            {

                long long tmpnum=mypow(saveprime[i],k);

                for(int j=tmpnum;j<=n;j++)

                {

                    dp[j]=max(tmp[j-tmpnum]*tmpnum,dp[j]);

                }

            }

        }

        cout<<dp[n];

        long long mx=dp[n];

        int anscnt=;

        int anssum=;

        for(int i=;i<;i++)

            saveans[i]=;

        for(int i=;i<=cnt;i++)

        {

            int sign=;

            while(mx%saveprime[i]==)

            {

                saveans[anscnt] *= saveprime[i];

                mx /= saveprime[i];

                sign=;

            }

            if(sign==)

            {

                anssum += saveans[ anscnt ];

                anscnt++;

            }

        }

        sort(saveans,saveans+anscnt);

        //printf("\n");

        //for(int i=0;i<anscnt;i++)

            //printf("%d ",saveans[i]);

        //printf("\n");

        for(int i=;i<=n-anssum;i++)

        {

            printf(" %d",i);

        }

        int pos=n-anssum;

        for(int i=;i<anscnt;i++)

        {

            for(int j=;j<=saveans[i];j++)

                printf(" %d",pos+j);

            printf(" %d",pos+);

            pos+=saveans[i];

        }

        printf("\n");

    }

    return ;

}

巴特西

poj 3590(dp 置换)

最新文章

热门文章