首页 > 其他分享 >那永恒没骗我 离散也没有 这份爱只是活在 另外时空

那永恒没骗我 离散也没有 这份爱只是活在 另外时空

时间:2022-09-23 22:57:04浏览次数:54  
标签:连边 没骗 然后 times 离散 枚举 端点 活在 dp

那永恒没骗我 离散也没有
这份爱只是活在 另外时空
如果 每一声再见 会开启
一个新的空间
每做一个梦 是时空 偶尔的重叠
你好吗 离开的人啊
请帮我 相爱到剧终
\(~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\) ——周深 《花开忘忧》

题意

\(~~~~\) 圆上有 \(2n\) 个点,保证任意选出六个点连边不会交于一点,求有多少连边方案使得连完过后恰有 \(n-1\) 个交点且这些交点形成一棵树.
\(~~~~\) \(1\leq n\leq 20\).

题解

\(~~~~\) 我宣布ubuntu的输入法就算是fcitx也很难用,想办法安个搜狗。

\(~~~~\) AT 的题不出意外会有一个思路然后这个思路出了意外。

\(~~~~\) 这题一开始想成共有 \(n\) 个点,自然而然考虑到状压。然后发现可以不关心已经选了的点怎么连的边,因为只要新连边的两个端点跨过了其中一个端点即可。于是有了美好的 \(\mathcal{O(2^n n^3)}\) 的算法,然后发现是 \(2n\) ,然后自闭。

\(~~~~\) 然后顺着刚刚的思路,我们只需要关心一个区间的端点中间只包含了一个连出去的边,所以我们定义 \(dp[l,r,x]\) 表示 \([l,r]\) 区间内 \(x\) 向区间外连边,其他内部连的方案数。

\(~~~~\) 然后考虑怎么转移这样一个东西过来,枚举状态 \([l,r,i]\) 用 \(n^3\) ,然后我们枚举两个端点 \(j,k\) 表示这两个端点连边,那么这个端点就会与已经枚举的 \(x\) 有交,这也是唯一的交。然后我们来看更其他的点。可以发现要么这些边的端点在 \(j\) 两侧,要么在 \(i\) 两侧,要么在 \(k\) 两侧。更进一步地,存在两个分割点 \(p,q\) ,使得 \([l,p]\) 内的互相连边,\([p+1,q-1]\) 内的互相连边,\([q,r]\) 内的互相连边,并且甚至我们已经确定了连出去的点,所以我们就得到了三个子问题。

\(~~~~\) 所以 \(dp_{l,i,r}=dp_{p+1,i,q-1}\times dp_{q,k,r} \times dp_{l,j,p}\times [a_{j,k}=1]\) ,这就有了 \(n^7\) 的转移。

\(~~~~\) 不过这东西常数挺小然后可以过。

\(~~~~\) 令 \(g_{l,k,p}=\sum f_{l,j,p}\times [a_{j,k}=1]\) ,这可以在每个状态过后用 \(n^2\) 完成。

\(~~~~\) 最后只需要每次枚举完状态过后 \(n^2\) 就可以了.

\(~~~~\) 最后再吐槽一次输入法

代码

#include <bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
    T f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
    x*=f;
}
char Map[45][45];
ll f[45][45][45],g[45][45][45];
int main() {
    #ifndef ONLINE_JUDGE
    freopen("input","r",stdin);
    freopen("output","w",stdout);
    #endif
    int n;read(n);n*=2;
    for(int i=1;i<=n;i++) scanf("%s",Map[i]+1);
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) Map[i][j]-='0';
    for(int i=2;i<=n;i++)
    {
        f[i][i][i]=1;
        for(int j=i+1;j<=n;j++) g[i][j][i]=Map[i][j];
    }
    for(int len=3;len<n;len+=2)
    {
        for(int l=2;l+len-1<=n;l++)
        {
            int r=l+len-1;
            for(int p=l;p<=r;p+=2)
            {
                for(int q=r;q>=l;q-=2)
                {
                    ll Tmp=0;
                    for(int k=q;k<=r;k++) Tmp+=g[l][k][p]*f[q][k][r];
                    for(int i=p+1;i<q;i++) f[l][i][r]+=f[p+1][i][q-1]*Tmp;
                }
            }
            for(int i=l;i<=r;i++)
                for(int j=i+1;j<=n;j++) g[l][j][r]+=Map[i][j]*f[l][i][r];
        }
    }
    ll Ans=0;
    for(int i=2;i<=n;i++) Ans+=Map[1][i]*f[2][i][n];
    printf("%lld",Ans);
    return 0;
}

标签:连边,没骗,然后,times,离散,枚举,端点,活在,dp
From: https://www.cnblogs.com/Azazel/p/16724588.html

相关文章

  • 离散数学中群、环、域的理解
    1、群(group)是两个元素作二元运算得到的一个新元素,需要满足群公理(groupaxioms),即:①封闭性:a∗bisanotherelementintheset②结合律:(a∗b)∗c=a∗(b∗......
  • 离散数学中 群的概念
    一.群的定义说起群,首先要引出一个更大的概念——代数系统(什么是代数系统就不解释了…),其中在概念上来看,代数系统>广群>半群独异点>群。设【<G,*>】是一个代数系统,其中G是......
  • 数字信号处理--第二章/离散时间信号和离散时间系统
    离散时间信号--数字序列离散时间信号的表示概述对于x(n):n为整数时有对应数值,n非整数时,x(n)没有定义,不可认定为0单位取样序列δ(n):n=0时值为1;单位冲激函数δ(t):n=0时值为∞......
  • 算法学习之路 离散化
    //离散化值得就是一一对应的关系,通常处理大数据范围中的小范围数据;离散化的中的两个步骤:1.a[]中可能的重复元素(去重)2.如何算出x离散化之后的值(二分)/*离散化模板......