UOJ Logo kczno1的博客

博客

cf 418 div_2 E

2017-06-07 23:17:29 By kczno1

迟了半个小时多才ak。。

我打的dp似乎是O(n^5)的(不过常数挺小的),应该不是最优的

考虑到距离序列

一定是一段一段的

每段每个点都向上一段连一条边,并可能存在段内互连

用dp[x][y1][y2][n1][n2]表示做到第x个点,上一段有y1个点还能连1条边,y2个点2条,当前段有n1个点1条,n2个点2条。

当y1=y2=0时,考虑把这个点新开一段

枚举他和当前段连的是2条的点还是1条的点

否则把这个点作为当前段

枚举他和上个段连的是2条的点还是1条的点

并枚举他和当前段内的连边

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int N=52,D=1e9+7,W1=50,W2=50*50,W3=50*50*50,W4=50*50*50*50;
int n;
int d[N];ll c[N][N];
map<int,int>f[N];

int dp(int x,int y1,int y2,int n1,int n2)
{
    if(y1<0||y2<0||n1<0||n2<0)return 0;
    if(x>n) return y1==0&&y2==0&&n1==0&&n2==0;

    int now=y1*W3+y2*W2+n1*W1+n2;
    if(f[x].count(now)) return f[x][now];

    ll ans=0;
    if(y1==0&&y2==0)
    {
        rep(x1,0,1)
        {
           int x2=1-x1;
           ans+=c[n1][x1]*c[n2][x2]%D*dp(x+1,n1-x1+x2,n2-x2,d[x]-x1-x2==1,d[x]-x1-x2==2);
        }
    }
    else
    {
        rep(x1,0,1)
        {
         int x2=1-x1;
        if(y1-x1+x2>=0&&x2<=y2)
        {
           int nd=d[x]-x1-x2;
           rep(nx1,0,nd)
           rep(nx2,0,nd-nx1)
            ans+=c[y1][x1]*c[y2][x2]%D*c[n1][nx1]%D*c[n2][nx2]%D*
            dp(x+1,y1-x1+x2,y2-x2,n1-nx1+nx2+(nd-nx1-nx2==1),
                                  n2-nx2+(nd-nx1-nx2==2));
        }
        }
    }
    return f[x][now]=ans%D;
}

int main()
{
    freopen("1.in","r",stdin);
    scanf("%d",&n);
    rep(i,1,n)scanf("%d",d+i);
    rep(i,0,n)
    {
       c[i][0]=1;    
       rep(j,1,i)c[i][j]=(c[i-1][j-1]+c[i-1][j])%D;
    }
    printf("%d\n",dp(3,d[1]==2,d[1]==3,d[2]==2,d[2]==3));
}

评论

xumingkuan
友情链接:官方题解 http://codeforces.com/blog/entry/52449
WrongAnswer
我想的DP似乎不太一样…… 我是记f(i,j)为[i,j)为某个BFS层,已确定[0,i)内的点之间及[0,i)和[i,j)之间的连边情况下,确定剩下的连边方案数。 转移时枚举下一段[j,k)的右端点k,记[i,j)内d=2的点有a个,d=3的点有b个,f(i,j)=∑f(j,k)g(a,b,k-j)。 其中g(i,j,k)为i+k个度为1的点,j个度为2的点,且k个度为1的点只能和另外i+j个点连边的方案数。 转移时,如果k>0就枚举k个点中的一个和哪个点连,否则如果i>0就枚举i个点中的一个和哪个点连,否则就是用若干个环覆盖j个点。 没打这场CF……后来写的: http://codeforces.com/contest/814/submission/27700153

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。