AtCoder Grand Contest 031 (AGC031) F - Permutation and Minimum 动态规划

概述原文链接www.cnblogs.com/zhouzhendong/p/AGC031F.html 草率题解 对于每两个相邻位置，把他们拿出来。 如果这两个相邻位置都有确定的值，那么不管他。 然后把所有的这些数拿出来，分为两类，一类是没有被填入的，一类是被填入的。 然后大力DP即可。由于没有被填入的可以任意排列，所以最后还要乘上一个阶乘。 代码 #include <bits/stdc++.h>#de

原文链接www.cnblogs.com/zhouzhendong/p/AGC031F.HTML

草率题解

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

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

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

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

代码

#include <bits/stdc++.h>#define clr(x) memset(x,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<<endl#define outtag(x) cerr<<"---------------"#x"---------------"<<endl#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";                        For(_x,R)cerr<<a[_x]<<" ";cerr<<endl;using namespace std;typedef long long LL;typedef vector <int> 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 <int> v;int main(){    n=read();    For(i,1,n*2){        a[i]=read();        if (a[i]!=-1)            b[a[i]]=1;    }    For(i,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,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,tot)        For(j,tot)            For(k,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);                }            }    int ans=dp[tot][0][0];    For(i,cnt)        ans=(LL)ans*i%mod;    cout<<ans<<endl;    return 0;}

总结

以上是内存溢出为你收集整理的AtCoder Grand Contest 031 (AGC031) F - Permutation and Minimum 动态规划全部内容，希望文章能够帮你解决AtCoder Grand Contest 031 (AGC031) F - Permutation and Minimum 动态规划所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。