CF888F Connecting Vertices

CF888F Connecting Vertices

题号很吉利我们把这个正多边形展开成一条线段，转化成经典区间DP问题。毕竟n³的算法也不是很多

然后，对于题目中要求两条连线不能相交，相当于线段上的两个区间要么相离，要么相切，要么包含。对于不能连的两个点，在DP的时候特判一下就行。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=666;
int dp[N][N][6],n,a[N][N];
const int mod=1e9+7;
signed main(){
    //l97gtl87fr8l
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) cin>>a[i][j];
        dp[i][i][0]=1;
    }
    for(int len=2;len<=n;len++){
        for(int l=1,r=len;r<=n;l++,r++){
            if(a[l][r]) {
                for(int k=l;k<r;k++){
                    dp[l][r][0]+=(dp[l][k][0]+dp[l][k][1])*(dp[k+1][r][0]+dp[k+1][r][1]);
                    dp[l][r][0]%=mod;
                }
            }
            for(int k=l+1;k<r;k++){
                if(!a[l][k]) continue;
                dp[l][r][1]+=dp[l][k][0]*(dp[k][r][0]+dp[k][r][1]);
                dp[l][r][1]%=mod;
            }
        }
    }
    cout<<(dp[1][n][0]+dp[1][n][1])%mod;
    //otf8o7fr8ol6fr8o6fr
    return 0;
}