CF Gym 100637K Microcircuits （DP）

题意：给你n个点，将这些点放在一个环上，问你不相交的连k条线的方案数。（没有重点）

题解：dp[i][j]表示i个点连j条线的方案数，那么新加一个点i，

情况1，i没有和之前的点相连，方案数为dp[i-1][j]；

情况2，i和p号点相连(0<p<j)，那么就划分成了两个环，然后枚举一些子问题的连边数，方案数为sum( dp[p-1][q]*dp[i-1-p][j-1-q] ) (0<=q<j)

时间复杂度为O(n^4)，也许可以和号优化

#include<cstdio>

#include<cmath>

#include<vector>

#include<map>

#include<set>

#include<algorithm>

using namespace std;

typedef long long ll;

//#define local

const int maxn = ;

ll dp[maxn][maxn];

int main()

{

#ifdef local

    freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

#endif // local

    int n,k;

    scanf("%d%d",&n,&k);

    for(int i = ; i <= n; i++) dp[i][] = ;

    for(int i = ; i <= n; i++ ){

        for(int j = ; j <=k; j++){

            dp[i][j] = dp[i-][j];

            for(int p = ; p < i; p++){ //枚举连到哪一个点

                for(int q = ; q < j; q++ ){    //枚举子问题的边数

                    dp[i][j] += dp[p-][q]*dp[i-p-][j--q];

                }

            }

        }

    }

    printf("%I64d",dp[n][k]);

    return ;

}

巴特西

CF Gym 100637K Microcircuits （DP）

最新文章

热门文章