有友情链接的网站,网站建设3d插件,windows优化大师免费版,做网站需要哪些条件解析
确实精妙的一道题。 卡在最后一步dp转化上了#xff0c;这个转化也确实是本题的难点。
当一个计数难以下手的时候#xff0c;先想想如何判合法#xff1f; 不难想到一个较为显然的贪心#xff1a;假如和上一个一样#xff0c;就填一个当前的最大值和最小值#xf…解析
确实精妙的一道题。 卡在最后一步dp转化上了这个转化也确实是本题的难点。
当一个计数难以下手的时候先想想如何判合法 不难想到一个较为显然的贪心假如和上一个一样就填一个当前的最大值和最小值否则不妨设变大如果 (bi,bi1)(b_i,b_{i1})(bi,bi1) 之间已经有数必然非法否则若 bi1b_{i1}bi1 未出现填它和最大值否则填最大和次大值。
把这个过程抽象为判定合法的条件
bi∈[ai,a2n−i]b_i\in [a_i,a_{2n-i}]bi∈[ai,a2n−i]∄ji,bj∈(bi−1,bi)\not \exists ji,b_j\in (b_{i-1},b_i)∃ji,bj∈(bi−1,bi)
第一条容易限制关键是第二条。 尝试对问题进行等价转化 倒序考虑每次把合法区间的数排序并去重并且把所有被 (ai,ai1)(a_i,a_{i1})(ai,ai1) 夹在中间的数删去剩下的数就是下次可以填的数。 进一步的可以看成维护一个集合 SSS第 i 次加入两个元素 ai,a2n−ia_i,a_{2n-i}ai,a2n−i然后把集合内 (ai,ai1)(a_i,a_{i1})(ai,ai1) 之间的元素删除。 这个就容易 dp 了。设 fi,l,rf_{i,l,r}fi,l,r 表示填第 i 位的时候集合内有 lll 个小于中位数的元素rrr 个大于中位数的元素的方案数枚举下一次中位数的位置转移即可。 复杂度 O(n4)O(n^4)O(n4)。 注意不要向集合内加入大小相同的元素。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
using namespace std;const int N105;
const int mod1e97;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}inline ll ksm(ll x,ll k){ll res(1);while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}int n,m;
int a[N1];
int f[N][N][N];
#define add(x,y) (xy,xmod?x-mod:0)signed main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifnread();for(int i1;i2*n-1;i) a[i]read();sort(a1,a12*n-1);f[n][0][0]1;ll ans(0);for(int in-1;i1;i--){int dl(a[i]!a[i1]),dr(a[2*n-i]!a[2*n-i-1]);for(int l0;l2*n-1;l){for(int r0;lr2*n-1;r){if(!f[i1][l][r]) continue;add(f[i][ldl][rdr],f[i1][l][r]);for(int k1;kldl;k){add(f[i][ldl-k][rdr1],f[i1][l][r]);}for(int k1;krdr;k){add(f[i][ldl1][rdr-k],f[i1][l][r]);}}}}for(int l0;l2*n-1;l){for(int r0;lr2*n-1;r) add(ans,f[1][l][r]);}printf(%lld\n,ans);return 0;
}
