2021-11-30训练赛D题题解

题目链接：https://codeforces.com/contest/1382/problem/D​​​​​​

考察方向：思维+DP；

题解：实际该题虽然说的是取最大值，然后把较小值放到最大值之前，但实际的意思是两值比较从小到大排序。

比如：A：3 2 8 4；B：6 1 5 7；

3 6比较取3，2 6比较取2，8 6比较取6，8 5比较取5，8 7比较取7，然后输出 8 4   

---总共输出 3 2 6 5 7 8 4.

由上可得就是找一个值后面比他大的第一个值，记录距离，跳到该值再次重复，直到到达最大值，记录最大值到最后的距离。

一开始我是想用特判来做，但发现情况太多，无法判断每一次的最大值应该在A还是B（从而无法判断是否存在合适的A和B）；

之后我发现可以把每个值看成只会出现一次，就演变成了经典的01背包。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N=4010;
int a[N],p[N];
int dp[N];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=2*n;i++)
{
scanf("%d",&a[i]);
}
memset(dp,0,sizeof(dp));
int tep=0;
dp[0]=1;
int cnt=1;
int r=1;
for(int i=2;i<=2*n;i++)
{
if(a[i]<a[r])
{
cnt++;
}
else
{
p[tep++]=cnt;
r=i;
cnt=1;
}
}
p[tep++]=cnt;
for(int i=1;i<tep;i++)
{
for(int j=n;j>=p[i];j--)
{
int num=dp[j-p[i]];
dp[j]=max(dp[j],num);
}
}
int num=dp[n];
if(num!=0)
{
printf("YESn");
}
else
{
printf("NOn");
}
}
return 0;
}

tips：注意每个数组都要开2*n的范围，否则会RE

最后

以上就是光亮酸奶为你收集整理的2021-11-30训练赛D题题解的全部内容，希望文章能够帮你解决2021-11-30训练赛D题题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。