路子是对了的,所有信息几乎都观察到了。但是最后的思路却错了。、
要避免思维太过于混乱
#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"; } }