AtCoder Grand Contest 030 (AGC030) F - Permutation and Minimum 动态规划
发布日期:2021-10-24 15:11:36 浏览次数:21 分类:技术文章

本文共 1896 字,大约阅读时间需要 6 分钟。

原文链接www.cnblogs.com/zhouzhendong/p/AGC030F.html

草率题解

对于每两个相邻位置,把他们拿出来。

如果这两个相邻位置都有确定的值,那么不管他。

然后把所有的这些数拿出来,分为两类,一类是没有被填入的,一类是被填入的。

然后大力DP即可。由于没有被填入的可以任意排列,所以最后还要乘上一个阶乘。

代码

#include 
    
     #define clr(x) memset(x,0,sizeof x)#define For(i,a,b) for (int i=(a);i<=(b);i++)#define Fod(i,b,a) for (int i=(b);i>=(a);i--)#define fi first#define se second#define pb(x) push_back(x)#define mp(x,y) make_pair(x,y)#define outval(x) cerr<<#x" = "<
     
      <
      
       <<"---------------"#x"---------------"<
       
        <<#a"["<
        
         <<".."<
         
          <<"] = ";\
          
For(_x,L,R)cerr< <<" ";cerr<  vi;LL read(){
LL x=0,f=0;
char ch=getchar();
while (!isdigit(ch))
f|=ch=='-',ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?-x:x;}const int N=305*2,mod=1e9+7;int Pow(int x,int y){
int ans=1;
for (;y;y>>=1,x=(LL)x*x%mod)
if (y&1)
ans=(LL)ans*x%mod;
return ans;}void Add(int &x,int y){
if ((x+=y)>=mod)
x-=mod;}void Del(int &x,int y){
if ((x-=y)<0)
x+=mod;}int Add(int x){
return x>=mod?x-mod:x;}int Del(int x){
return x<0?x+mod:x;}int n;int a[N],b[N];int cnt=0,tot=0;int dp[N][N][N];vector   v;int main(){
n=read();
For(i,1,n*2){
a[i]=read();
if (a[i]!=-1)
b[a[i]]=1;
}
For(i,1,n){
if (a[i*2-1]==-1&&a[i*2]==-1)
cnt++,tot+=2;
else if (a[i*2-1]==-1)
tot+=2,v.pb(a[i*2]);
else if (a[i*2]==-1)
tot+=2,v.pb(a[i*2-1]);
}
For(i,1,n*2)
if (!b[i])
v.pb(i);
sort(v.begin(),v.end());
v.pb(0);
reverse(v.begin(),v.end());
dp[0][0][0]=1;
For(i,1,tot)
For(j,0,tot)
For(k,0,tot){
int val=dp[i-1][j][k];
if (!val)
continue;
if (!b[v[i]]){
Add(dp[i][j+1][k],val);
if (j>0)
Add(dp[i][j-1][k],val);
if (k>0)
Add(dp[i][j][k-1],(LL)val*k%mod);
}
else {
Add(dp[i][j][k+1],val);
if (j>0)
Add(dp[i][j-1][k],val);
}
}
int ans=dp[tot][0][0];
For(i,1,cnt)
ans=(LL)ans*i%mod;
cout< <
return 0;}

转载于:https://www.cnblogs.com/zhouzhendong/p/AGC030F.html

转载地址:https://blog.csdn.net/weixin_30800807/article/details/94933531 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:[原创]通过IE8的测试来看CSS选择符的样式渲染优先级
下一篇:python实现邮件接口——smtplib模块

发表评论

最新留言

逛到本站,mark一下
[***.249.68.78]2022年04月16日 17时35分47秒