区间DP 等腰三角形

题目描述：给定一个正N边形，可以通过连线将这个多边形分割成N-2个三角形，问这N-2个三角形中恰有k个等腰三角形的分割方法有多少？这个值可能很大，输出对9397取模的结果。
数据范围：n，k <= 50.

这道题也是区间DP，不过稍微难一点。

首先我们先想个办法判断等腰三角形，因为这是一个正多边形，所以我们对于三个点，我们可以计算一下他们的差的绝对值，直接比较这个是否相同即可。

之后就是怎么DP了，想到刚才的三角划分，这题应该也是一道区间DP。令dp[i][j][k]表示在区间i～j之内划分出k个等腰三角形的方案数，之后我们枚举一下端点，判断一下新的断点能否形成等腰三角形进行转移。

这样的复杂度是O（n3*k2）的，会超时，我们考虑优化。因为这是一个正多边形，所以我们可以直接用dp[i][j]表示把以i个连续点为顶点的正多边形划分出j个等腰三角形的方案数。之后直接枚举从几个连续点的位置断开进行转移即可，这样复杂度被优化到了O（n²k²），可以过。

如果不大理解的话，可以结合凸多边形三角划分这道题想一想。

看一下代码。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<set>

#include<queue>

#define rep(i,a,n) for(int i = a;i <= n;i++)

#define per(i,n,a) for(int i = n;i >= a;i--)

#define enter putchar('\n')

using namespace std;

typedef long long ll;

const int M = ;

const ll INF = ;

const int mod = ;

int read()

{

    int ans = ,op = ;

    char ch = getchar();

    while(ch < '' || ch > '')

    {

    if(ch == '-') op = -;

    ch = getchar();

    }

    while(ch >= '' && ch <= '')

    {

    ans *= ;

    ans += ch - '';

    ch = getchar();

    }

    return ans * op;

}

int n,k,dp[][];

bool judge(int x,int m)

{

   int ta = min(x - ,n - x + ),tb = min(m - ,n - m + ),tc = min(m - x,n - m + x);

   return (ta == tb || tb == tc || ta == tc);

}

int dfs(int n,int k)

{

   if(dp[n][k] != -) return dp[n][k];

   if(n <= ) return ;

   int cur = ;

   rep(x,,n-)

   {

      rep(j,,k-judge(x,n)) cur += dfs(x,j) * dfs(n-x+,k-j-judge(x,n)),cur %= mod;

   }

   return dp[n][k] = cur;

}

int main()

{

   n = read(),k = read();

   memset(dp,-,sizeof(dp));

   dp[][] = ;

   printf("%d\n",dfs(n,k));

   return ;

}

巴特西

区间DP 等腰三角形

最新文章

热门文章