Codeforces Round #658 (Div. 2)D(01背包)

题意：给定随意俩个数组的合并规则，每次取俩个数组第一个的最小值，直至俩数组为空.。给定目标数组（1~n出现1次）问能不能2个数组合并成目标数组

分析：可以把目标数组分成若干段，要是能每段都连续给到且某些段能刚好凑成n的大小，那么问题就可以解决；

　　　而要达到“每段连续给到”：遍历目标数组取“连续降序段”。

　　　而要达到“某些段能刚好凑成n的大小”：对“连续降序段”的大小进行01背包，看dp[n]是不是恰好为n。

#include<bits/stdc++.h>using namespace std;#define pb push_back#define MP make_pairtypedef long long ll;typedef unsigned long long ull;const int mod=998244353;const int inf=0x3f3f3f3f;const ll INF=1e18;const int M=4e3+3;int dp[M],a[M],w[M];int main(){    int t;    scanf("%d",&t);    while(t--){        int n;        scanf("%d",&n);        for(int i=0;i<=n;i++)            dp[i]=0;        for(int i=1;i<=2*n;i++)            scanf("%d",&a[i]);        int maxx=a[1];        int countt=1,tot=0;        for(int i=2;i<=2*n;i++){            if(maxx>a[i])countt++;            else{                w[tot++]=countt;                countt=1;                maxx=a[i];            }        }        w[tot++]=countt;        sort(w,w+tot);        for(int i=0;i<tot;i++)            for(int j=n;j>=w[i];j--)                dp[j]=max(dp[j],dp[j-w[i]]+w[i]);        if(n==dp[n])            puts("YES");        else            puts("NO");    }    return 0;}

View Code