B. Unmerge

路子是对了的,所有信息几乎都观察到了。但是最后的思路却错了。、
要避免思维太过于混乱

#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";
    }
}
全部评论

相关推荐

头像
11-18 16:08
福州大学 Java
影流之主:干10年不被裁,我就能拿别人一年的钱了,日子有盼头了
点赞 评论 收藏
分享
2 收藏 评论
分享
牛客网
牛客企业服务