Codeforces Round #658 (Div. 2) D. Unmerge (思维,01背包)

题意:有两个数组\(a\)和\(b\),每次比较它们最左端的元素,取小的加入新的数组\(c\),若\(a\)或\(b\)其中一个为空,则将另一个全部加入\(c\),现在给你一个长度为\(2n\)的数组\(c\),问是否能有两个长度为\(n\)的数组\(a\)和\(b\)构成.
题解:我们从左向右看\(c\),记一个最大值\(mx\),观察样例不难发现,跟随在\(mx\)后面比\(mx\)小的元素,它们一定来自同一个数组,比如第三个样例:
```
3 2 6 1 5 7 8 4
```
\(3,2\)一定来自同一个数组,\(6,1,5\)一定来自同一个数组,\(7\)就一个元素,\(8,4\)一定来自同一个数组,所以我们将它们分段,\((3,2)\),\((6,1,5)\),\((7)\),\((8,4)\).我们要在这些之间凑出一个元素长度为\(n\)的数组即可,这里我们用01背包来解决,我们背包的最大容量为\(n\),去看是否能填满.

代码:

int t;

int n;

int a[N];

vector<int> v;

int dp[N];

int main() {

    scanf("%d",&t);

     while(t--){

     	scanf("%d",&n);

     	me(dp,0,sizeof(dp));

     	v.clear();

     	for(int i=1;i<=2*n;++i){

     		scanf("%d",&a[i]);

     	}

     	int mx=a[1];

     	int pos=1;

     	for(int i=2;i<=2*n;++i){

     		if(a[i]>mx){

     			v.pb(i-pos);

     			mx=a[i];

     			pos=i;

     		}

     	}

     	v.pb(2*n+1-pos);

     	for(int i=0;i<v.size();++i){

     		for(int j=n;j>=v[i];--j){

     			dp[j]=max(dp[j],dp[j-v[i]]+v[i]);

     		}

     	}

     	if(dp[n]==n) puts("YES");

     	else puts("NO");

     }

    return 0;

}

巴特西

Codeforces Round #658 (Div. 2) D. Unmerge (思维,01背包)

最新文章

热门文章