1046: [HAOI2007]上升序列

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1046

先求最长上升子序列中的d数组（d[i]表示以第i个数开头的最长的LIS的长度）。
每一个询问，如果比最长上升子序列长度大就无解，否则有解。
对于一个询问m，答案序列的第i位s[i]为：从答案序列的上一位+1开始的第一个j使得a[j]>s[i-1]并且d[j]>=m-i的a[j]。
输出的时候注意不要有行末空格不然会PE……
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
const int MaxN=10001;

int n,m,a[MaxN],d[MaxN];
int s[MaxN];

void init()
{
    cin>>n;
    for (int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    cin>>m;
}

void treat()
{
    for (int i=n-1;i>=0;i--)
    {
        for (int j=i+1;j<n;j++)
        {
            if (a[i]<a[j]) d[i]=max(d[i],d[j]);
        }
        d[i]++;
        //cout<<d[i]<<' ';
    }
    //cout<<endl;
}

void work(int k)
{
    int j=0;
    for (int i=k;i>0;i--)
    {
        for (;j<n && (d[j]<i || (k!=i && a[j]<=s[k-i-1]));j++);
        if (j==n)
        {
            printf("Impossible\n");
            return;
        }
        s[k-i]=a[j];
        j++;
    }
    for (int i=0;i<k-1;i++)
    {
        printf("%d ",s[i]);
    }
    printf("%d\n",s[k-1]);
}

int main()
{
    init();
    treat();
    for (int i=0;i<m;i++)
    {
        int k;
        cin>>k;
        work(k);
    }
    return 0;
}

posted on 2013-02-14 18:11 Kiro 阅读(154) 评论(0)  编辑 收藏 引用 所属分类: 衡八oj

只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理