C2. Prefix Flip (Hard Version)
题意
给出一个长度为2n的排列p
要求判断能否还原出两个等长的数组a b
使得merge(a,b)=p
定义merge运算：
merge(空集,a)=a
merge(a[1~n] , b[1~n])= a[1]<b[1]?a[1]+merge(a[2~n], b[1~n]) : b[1]+ merge(a[1~n], b[2~n]);
就是比较a和b数组第一个数谁大 就把谁放到新数组(最初为空)的下一个位置
题解
观察样例发现merge运算实际上是当 max(a[l~r]) <b[i] or max(b[l~r]) < a[i]时，
将a[l~r]/ b[l~r] 放在一个b[i]/a[i]前
根据这个性质将2n的排列p打碎成尽量多的子串 假设最后子串有m个
例如3 , 1 , 4 ,5 , 2 , 63. 这个例子被分为(3 , 1) , (4) , (5 , 2) ,(6)
每一个子串属于a/b中的1个 现在可以将问题转化成01背包模型
对于一个容量为n的 背包 m个物品每个 物品体积=价值=这个子串的长度
求能装下物品的前提下最大价值
若最后dp[n]=n说明存在解 否者输出no
参考博客
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const int mod=2e3;
const int Max=4000+5;
int data[Max],dp[Max];
string s,ns;int n;
int main(){
Turnoff;
int t;cin>>t;
while(t--){
int n;cin>>n;
vector<int>group;int cnt=1;
for(int i=0;i<2*n;i++)cin>>data[i],dp[i]=0;
int maxn=data[0];data[2*n]=2*n+1;
for(int i=1;i<=2*n;i++){
if(data[i]>maxn){
group.push_back(cnt);
cnt=1;
}
else cnt++;
maxn=max(maxn,data[i]);
}
int len=group.size();
for(int i=0;i<len;i++){
for(int w=n;w>=group[i];w--){
dp[w]=max(dp[w],dp[w-group[i]]+group[i]);
}
}
if(dp[n]!=n)cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
}
|