首先将序列排序,这是显然的。
考虑倒着确定 \(b\) 序列中的每个数。即从完整的 \(a\) 序列开始,每次删掉两个数,记录中位数。
先找出 \(b\) 序列合法的条件。容易发现对于所有 \(i\),在 \(b_{p_i}\) 成为中位数时,\(p_i,p_{i+1}\) 之间的所有数都已经被删除了,且 \(i\le p_i\le 2n-i\)。
考虑 dp,记 \(f_{i,j,k}\) 表示当前确定了 \(b\) 的后 \(i\) 个值,当前区间左边有 \(j\) 个可能作为这个数,右边有 \(k\) 个也可能作为这个数,直接枚举取哪个数转移即可。注意到可能存在重复的值,假设 \(a_l\) 和 \(a_{l-1}\) 相同,那么此时统一取 \(a_l\) 即可,右边同理。
参考代码:
#include<bits/stdc++.h>
#define md 1000000007
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rept(i,a,b) for(int i=(a);i<(b);++i)
#define drep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
int n,ans,a[103],f[53][103][103];
signed main(){
cin>>n;
rept(i,1,n<<1)cin>>a[i];
sort(a+1,a+n+n);
f[n][0][0]=1;
drep(i,n-1,1){
int c1=a[i]!=a[i+1],c2=a[n*2-i]!=a[n*2-i-1];
rept(j,0,n<<1){
rept(k,0,n<<1)if(f[i+1][j][k]){
f[i][j+c1][k+c2]=(f[i][j+c1][k+c2]+f[i+1][j][k])%md;
rept(x,0,j+c1)f[i][x][k+c2+1]=(f[i][x][k+c2+1]+f[i+1][j][k])%md;
rept(x,0,k+c2)f[i][j+c1+1][x]=(f[i][j+c1+1][x]+f[i+1][j][k])%md;
}
}
}
rept(i,0,n<<1)rept(j,0,n<<1)ans=(ans+f[1][i][j])%md;
cout<<ans;
return 0;
}
标签:AGC012F,le,int,题解,Prefix,序列,103,define
From: https://www.cnblogs.com/zifanoi/p/18540013