相当好的一道思维小清新风格的背包题(没想到吧
首先我们要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;
}
Comments | NOTHING