首页 > 其他分享 >Codeforces Round #658 (Div. 1) B

Codeforces Round #658 (Div. 1) B

时间:2022-10-31 16:56:17浏览次数:64  
标签:const int Codeforces st 658 Div now dp

B. Unmerge

看完样例发现
3 1 2 4
3后面跟着的1 2肯定是和3一组的
因为他们不如3大所以他们一定是被直接排出来的
就这样我们可以将这个序列分成好多组
然后就是金典背包 选与不选
注意的是他的n是2000 然后序列就是4000 所以我们数组要开成4000

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
const int M = 998244353;
const int mod = 1e9+7;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int dp[5010][5010];
void solve(){
    int n;cin>>n;n<<=1;
    vector<int>a(n+10),v(1),st;
    int now=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]>now){
            now=a[i];
            st.push_back(i);
        }
    }
    st.push_back(n+1);
    for(int i=1;i<st.size();i++){
        v.push_back(st[i]-st[i-1]);
    }
    for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)dp[i][j]=0;
    dp[0][0]=1;
    for(int i=1;i<v.size();i++){
        for(int j=1;j<=n;j++){
            if(j-v[i]>=0)dp[i][j]|=dp[i-1][j-v[i]];
            dp[i][j]|=dp[i-1][j];
        }
    }
    if(dp[(int)v.size()-1][n/2])YES else NO
}
signed main(){
    fast
    int t;t=1;cin>>t;
    while(t--) {
        solve();
    }
    return ~~(0^_^0);
}

标签:const,int,Codeforces,st,658,Div,now,dp
From: https://www.cnblogs.com/ycllz/p/16844914.html

相关文章