上升序列

Posted on In

题目大意:在一个序列里面找一个字典序最小的指定长度的上升序列

题目来源:P2215

一反常态,这次需要从后往前找.

我们定义\(f_i\)为从第i个元素后最长上升的序列长度

然后遇到制定可以满足答案的就跳

因为是顺序查找,所以我们一旦遇到答案就去跳,一定是有解且最优的!

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;

const int N = 1e4 + 6;

int n, m, maxv;
int a[N], f[N];

signed main()
{
    int i, j; n = read();
    for (i = 1; i <= n; ++ i) a[i] = read();
    for (i = n; i >= 1; -- i)
    {
        f[i] = 1;
        for (j = i + 1; j <= n; ++ j) if (a[j] > a[i])
            f[i] = max(f[i], f[j] + 1);
        maxv = max(maxv, f[i]);
    }
    m = read();
    while (m --)
    {
        int l = read();
        if (l > maxv) {puts("Impossible"); continue;}
        int las = -1;
        for (i = 1; i <= n; ++ i)
        {
            if (f[i] >= l && a[i] > las)
            {
                put(a[i]), las = a[i];
                if (! -- l) break;
            }
        }
        puts("");
    }
    return 0;
}

后记:

考场上几乎想到了,但是差一点.

我是倒着搞的,贪心的正确性没办法保证.