CF1381B Unmerge

link

相当好的一道思维小清新风格的背包题（没想到吧

首先我们要dp的目标是能不能构造一个符合题目要求的数组

这dp的东西很不dp

仔细阅读题面不难知道，这个merge操作的本质就是两个数组比较第一个数，然后把两个数中小的那个加到排列p里

通过样例1：
4
3 2 6 1 5 7 8 4
我们按照 {3 2} {6 1 5} {7} {8 4}来划分这个排列
假如在一个排列中的最大值为max，次大值为smax,
通过观察我们可以发现在merge后的排列中，在max前面smax后面的数在merge前的数组中依然是在这样的位置上

所以我们可以提前把排列划分好几个小段，分别记下它们的长度

这样问题的就变成了用这些长度能不能填满两个长度为n的数组

于是跑一边01存在性背包就可以了

不得不说这题还是很妙de

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 4000 + 5;

int n, t;
int a[SIZE], f[SIZE][SIZE], siz[SIZE];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void solve()
{
    // memset(f, 0, sizeof(f)); 
    int cnt = 0, maxNum = 0, m = 0, tmp = 0, pos = 0;
    for (int i = 1; i <= n * 2; ++ i) {
        if (i == 1) tmp = a[i], cnt = 1;
        if (a[i] > maxNum) pos = i, maxNum = a[i];
        if (a[i] > tmp) siz[++ m] = cnt, tmp = a[i], cnt = 1;
        if (a[i] < tmp) ++ cnt;
    }
    if (pos < n) { 
        puts("NO");
        return;
    }
    siz[++ m] = cnt;
    f[0][0] = 1;
    for (int i = 1; i <= m; ++ i) {
        for (int j = 0; j <= n; ++ j) {
            f[i][j] = 0;
            if (j >= siz[i]) f[i][j] += f[i - 1][j - siz[i]];
            f[i][j] += f[i - 1][j];
        }
    }
    if (f[m][n]) printf("YES\n");
    else printf("NO\n");
}

int main()
{
    t = read();
    while (t --) {
        n = read();
        for (int i = 1; i <= n * 2; ++ i) a[i] = read();
        solve();
    }
    return 0;
}