题解归档 - cf888F

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf888F
• 本地来源：problems/cf888F/idea.md
• 题目链接：https://codeforces.com/contest/888/problem/F
• 原始标题：888F Connecting Vertices

思路

888F Connecting Vertices

题意

正 (n) 边形顶点 (1..n) 逆时针编号。可在部分顶点对之间连边（矩阵 a[i][j]=1 表示 (i,j) 可直连）。要连 (n-1) 条边使全体连通，且任意两条边除端点外不相交。求方案数 mod (10^9+7)。

思路

凸多边形上的区间 DP（非 meet-in-the-middle；Catalog 条目标签有误）。

关键观察：在凸多边形上，若边 ((i,j)) 被使用，则弧 ((i,j)) 内的点与弧外点只能通过 (i,j) 连通，子问题在区间上独立。

设 dp[i][j][0/1]：只考虑顶点 (i..j)（按逆时针顺序），连成一连通块，且 不/有 使用边 ((i,j)) 的方案数。dp[i][i][0]=1。

• 无 ((i,j)) 边：枚举 (i) 在区间内「最后连到的右端点」(k)（(i<k\le j)），先经 ((i,k)) 连通左侧，再处理 ([k,j])：
  [
  dpi[0] \mathrel{+}= dpi[1] \cdot (dpk[0]+dpk[1])
  ]
• 有 ((i,j)) 边（需 a[i][j]）：边 ((i,j)) 把区间拆成 ([i,k]) 与 ([k+1,j]) 两块，分别连通后拼起来：
  [
  dpi[1] \mathrel{+}= (dpi[0]+dpi[1]) \cdot (dpk+1[0]+dpk+1[1]),\quad k\in[i,j-1]
  ]

答案：((dp1[0]+dp1[1]) \bmod 10^9+7)。按区间长度递增转移，(O(n^3))。

模板

lib/动态规划(凸多边形区间DP).cpp（源自本题 AC 代码）。

复杂度

• 时间：(O(n^3))，(n\le 500)
• 空间：(O(n^2))

验证

• 官方样例：✅（(n=4) 全连边 → 12）
• 对拍：stress.py cf888F -n 200 ✅

lib_target

Catalog 原标注 meet in the middle 与题面不符；已沉淀 凸多边形区间 DP 模板。

代码

来源：problems/cf888F/solution.cpp

/* Author: likely
 * Time: 2026-06-08 02:54:53
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=505,mod=1000000007;
ll n,a[maxn][maxn],dp[maxn][maxn][2],i,j,k,len,cur,ans;
int main(){
    cin>>n;
    for(i=1;i<=n;i++){
        dp[i][i][0]=1;
        for(j=1;j<=n;j++) cin>>a[i][j];
    }
    for(len=2;len<=n;len++){
        for(i=1,j=len;j<=n;i++,j++){
            for(k=i+1;k<=j;k++){
                cur=(dp[k][j][0]+dp[k][j][1])%mod;
                dp[i][j][0]=(dp[i][j][0]+dp[i][k][1]*cur)%mod;
            }
            if(a[i][j]){
                for(k=i;k<j;k++){
                    cur=(dp[i][k][0]+dp[i][k][1])%mod;
                    ans=(dp[k+1][j][0]+dp[k+1][j][1])%mod;
                    dp[i][j][1]=(dp[i][j][1]+cur*ans)%mod;
                }
            }
        }
    }
    cout<<(dp[1][n][0]+dp[1][n][1])%mod<<"\n";
    return 0;
}