AT2366-[AGC012F]Prefix Median【dp】
2022/8/4 23:27:23
本文主要是介绍AT2366-[AGC012F]Prefix Median【dp】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
正题
题目链接:https://www.luogu.com.cn/problem/AT2366
题目大意
有一个长度为\(2n-1\)的序列\(a\),你可以将其重新排列,定义\(b_i\)为\(a_{1\sim 2i-1}\)的中位数。
询问有多少种不同的可能的\(b\)序列。
\(1\leq n\leq 50\)
解题思路
先假设\(a\)中所有数字都不同,我们去考虑一下\(b\)的限制。
相当于我们每次在\(a_i\)中加入两个数字\(x,y\),然后如果\(x,y\)都小于最后一个\(b\)则新的\(b\)取它在\(a\)中的前驱,如果都大于则取后继,如果一大一小则不动。
基于这个限制我们得到的条件是每次\(b_i\)加入数字之后的排名只能变动一位,这是充要的。
考虑去形式化这个条件,将\(a\)排序后,我们有:
- \(a_{n-i+1}\leq b_i\leq a_{n+i-1}\)
- 不存在\(j<i\)满足\(b_i<b_j<b_{i+1}\)或\(b_{i+1}<b_j<b_i\)
这样我们其实并不需要考虑\(a\)填的情况,如果\(b\)一次向外跨过了很多个\(a\),那么我们可以视这些\(a\)此时还没有加入,我们只需要限制往内跨的情况出现就好了。
不过这第二个条件依旧不好处理,我们考虑倒着做,那当我们确定一个\(b_i\)和\(b_{i+1}\)之后,相当于\((b_i,b_{i+1})\)之间的数字就都不能选择了。
考虑\(dp\),设\(f_{i,l,r}\)表示目前填了\(i\)个,对于现在的\(b_i\)来说,左边还剩下\(l\)个位置,右边还剩下\(r\)个位置。
然后每次加入两边的\(a_i\),如果\(a_{l}=a_{l+1}\),那么我们将其视为同一个,右边同理。
时间复杂度:\(O(n^4)\)
code
#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=110,P=1e9+7; ll n,m,a[N],f[N][N][N]; signed main() { scanf("%lld",&n);m=2*n-1; for(ll i=1;i<=m;i++) scanf("%lld",&a[i]); sort(a+1,a+m+1); f[n][0][0]=1; for(ll i=n-1;i>=1;i--){ ll l=i,r=2*n-i; ll dl=(a[l]!=a[l+1]),dr=(a[r]!=a[r-1]); for(ll l=0;l<=m;l++) for(ll r=0;r<=m;r++){ if(!f[i+1][l][r])continue; (f[i][l+dl][r+dr]+=f[i+1][l][r])%=P; for(ll k=0;k<l+dl;k++)(f[i][k][r+dr+1]+=f[i+1][l][r])%=P; for(ll k=0;k<r+dr;k++)(f[i][l+dl+1][k]+=f[i+1][l][r])%=P; } } ll ans=0; for(ll i=0;i<=m;i++) for(ll j=0;j<=m;j++) (ans+=f[1][i][j])%=P; printf("%lld\n",ans); return 0; }
这篇关于AT2366-[AGC012F]Prefix Median【dp】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升