路子是对了的,所有信息几乎都观察到了。但是最后的思路却错了。、
要避免思维太过于混乱
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int a[4100];
int b[4100];
bool dp[4100][4100];
int main() {
ios::sync_with_stdio(0);
int T;cin >> T;
dp[0][0] = 1;
while (T--) {
int n;cin >> n;
for (int i = 1;i <= 2 * n;++i)cin >> a[i];
int top = 0;
for (int rgt = 1, lft = 0;rgt <= 2 * n;++rgt) {
if (a[rgt] > a[lft]) {
b[++top] = 1;
lft = rgt;
}
else ++b[top];
}for (int i = 1;i <= top;++i) {
for (int j = 0;j <= n;++j) {
dp[i][j] = dp[i - 1][j];
if (j >= b[i])dp[i][j] |= dp[i - 1][j - b[i]];
}
}dp[top][n] ? cout << "YES\n" : cout << "NO\n";
}
}
京公网安备 11010502036488号