首页 > ACM题库 > HDU-杭电 > HDU 4377-Sub Sequence[解题报告]HOJ
2015
05-24

HDU 4377-Sub Sequence[解题报告]HOJ

Sub Sequence

问题描述 :

Recently, YCC is studying sequence problems. And he is struggling with it!!!= =
For such an ACMer like you, it is commonly believed that you must know the Longest Increasing Subsequence problem. Now Let’s define some useful functions and symbols:
Let U(A) be the length of the longest increasing subsequence of the original sequence A;
Let D(A) be the length of the longest decreasing subsequence of the original sequence A;
Let H(A) be the maximum value of U(A) and D(A), that is H(A) = max{U(A), D(A)}.
H(A)!!! Ah… Zauber anzahl, ist es nicht?
Now YCC wants to study the attributes of all the permutations of integer numbers from 1 to N. He wants to get such permutation P having minimum H(P). If more than one permutation satisfies the condition, you should give the lexicographically smallest one.

输入:

The first line contains an integer T which indicates the number of test cases.
The following T lines each contain an integer N (1 ≤ N ≤ 100000).

输出:

The first line contains an integer T which indicates the number of test cases.
The following T lines each contain an integer N (1 ≤ N ≤ 100000).

样例输入:

3
1
2
3

样例输出:

1
1 2
1 3 2

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
using namespace std;

#define MAXN 1005
bool vis[MAXN];
int a[MAXN], ant[MAXN];
int n;

int UU()
{
    int dp[MAXN], ans = 1;
    for(int i = 1; i <= n; i++) dp[i] = 1;
    for(int i = 1; i <= n; i++)
    {
        int MAX = 0;
        for(int j = i-1; j >= 1; j--)
        {
            if(a[i] > a[j] && dp[j] > MAX) MAX = dp[j];
        }
        dp[i] = MAX + 1;
        if(dp[i] > ans) ans = dp[i];
    }
    return ans;
}

int DD()
{
    int dp[MAXN], ans = 1;
    for(int i = 1; i <= n; i++) dp[i] = 1;
    for(int i = 1; i <= n; i++)
    {
        int MAX = 0;
        for(int j = i-1; j >= 1; j--)
        {
            if(a[i] < a[j] && dp[j] > MAX) MAX = dp[j];
        }
        dp[i] = MAX + 1;
        if(dp[i] > ans) ans = dp[i];
    }
    return ans;
}

int mmm = 99999;

void dfs(int x, int num)
{
    //if(tar) return;
    a[num] = x;
    if(num == n)
    {
        int MAX = UU();
        int MIN = DD();
        //printf("MAX=%d MIN=%d\n", MAX, MIN);
        int tp = max(MAX, MIN);
        if(tp < mmm)
        {
            mmm = tp;
            for(int i = 1; i <= n; i++)
            {
                ant[i] = a[i];
            }
        }
        return ;
    }
    for(int i = 1; i <= n; i++)
    {
        if(vis[i]) continue;
        vis[i] = true;
        dfs(i, num+1);
        vis[i] = false;
    }
}

int main()
{
    int i, j, t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        /*memset(vis, false, sizeof(vis));
        mmm = 99999;
        for(i = 1; i <= n; i++)
        {
            vis[i] = true;
            dfs(i, 1);
            vis[i] = false;
        }
        for(i = 1; i <= n; i++)
        {
            printf("%d ", ant[i]);
        }
        printf("\n------------------\n");*/

        if(n == 1) {printf("1\n");continue;}
        if(n == 2) {printf("1 2\n");continue;}
        if(n == 3) {printf("1 3 2\n"); continue;}
        /*if(n == 4) {printf("2 1 4 3\n"); continue;}
        if(n == 5) {printf("1 2 5 4 3\n"); continue;}
        if(n == 6) {printf("1 3 2 6 5 4\n"); continue;}
        if(n == 8) {printf("2 1 5 4 3 8 7 6\n"); continue;}
        if(n%2 == 1)
        {
            printf("1");
            for(i = 2; i <= (n+1)/2-3; i++)
            {
                printf(" %d", i);
            }
            printf(" %d %d %d", (n+1)/2, (n+1)/2-1, (n+1)/2-2);
            for(i = n; i >= (n+1)/2+1; i--)
            {
                printf(" %d", i);
            }
            printf("\n");
        }
        else
        {
            printf("1");
            for(i = 2; i <= n/2+1-4; i++)
            {
                printf(" %d", i);
            }
            printf(" %d %d %d %d", n/2+1, n/2, n/2-1, n/2-2);
            for(i = n; i >= n/2+2; i--)
            {
                printf(" %d", i);
            }
            printf("\n");
        }*/
        int l, kuai, sheng, tp;
        l = sqrt(n*1.0);
        bool tar = true;
        if(l == sqrt(n*1.0))
        {
            sheng = 0;
            kuai = n / l;
            tar = false;
            ///printf("goto L\n");
            goto L;
        }

        if(l != sqrt(n*1.0)) l++;
        kuai = n / l;
        sheng = n - kuai*l;
        if(sheng == 0 && l != sqrt(n*1.0))
        {
            sheng = l;
            kuai--;
        }
        //tp = l - kuai;
        //tp = min(tp, sheng)-1;

        //printf("l=%d kuai=%d sheng=%d\n", l, kuai, sheng);

        if(l - kuai >= 2)
        {
            printf("1");
            for(i = sheng; i > 1; i--)
                printf(" %d", i);
        }
        else
        {
            printf("%d", sheng);
            for(i = sheng-1; i >= 1; i--)
                printf(" %d", i);
        }
        /*for(i = 1; i <= tp; i++)
        {
            printf("%d ", i);
        }
        if(sheng-tp==0) goto L;
        for(i = sheng; i > sheng-tp; i--)
        {
            printf("%d ", i);
        }*/
        L:
        int sum = sheng;
        for(i = 1; i <= kuai; i++)
        {
            for(j = 0; j < l; j++)
            {
                if(tar) printf(" ");
                tar = true;
                printf("%d", sum+l-j);
            }
            sum += l;
        }
        printf("\n");
    }

    return 0;
}