poj3597 Polygon Division +动态规划+递推公式+公式转化技巧

绝地灬酷狼 2022-07-16 07:53 184阅读 0赞

poj3597 Polygon Division +动态规划+递推公式+公式转化技巧 题目链接：[http://poj.org/problem?id=3597][http_poj.org_problem_id_3597]

题面描述：

Polygon Division

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;2000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;131072K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;1335</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;711</td> 
  </tr> 
 </tbody> 
</table>

Description

Given a regular polygon, there are numerous ways to divide it into several triangles and/or quadrangles by adding some diagonals that do not properly intersect each other. For example, Figure 4 shows all ten different divisions of a regular pentagon into triangles and quadrangles.

![3597_1.png][]

Figure 4: Divisions of a regular pentagon into triangles and quadrangles

Given *n*, the number of sides of the polygon, compute the number of such divisions.

Input

The input contains multiple test cases. Each test case consists of a single integer *n* (3 ≤ *n* ≤ 5000) on a separate line. The input ends where EOF is met.

Output

For each test case, print the answer modulo 264 on a separate line.

Sample Input

3
    4
    5
    6
    7
    8
    9
    10

Sample Output

1
    3
    10
    38
    154
    654
    2871
    12925

题目大意：

此题要求将一个多边形划分成多个三角形或者四边形的不同的划分的方法，特别注意：数据库范围。

题目分析：

首先分析一下数据范围，各种数据类型的数据范围如下：

unsigned int 0～4294967295

**int 2147483648～2147483647  
unsigned long 0～4294967295  
long 2147483648～2147483647  
long long的最大值：9223372036854775807  
long long的最小值：-9223372036854775808  
unsigned long long的最大值：18446744073709551615**

**\_\_int64的最大值：9223372036854775807  
\_\_int64的最小值：-9223372036854775808  
unsigned \_\_int64的最大值：18446744073709551615**

所以对于对2e64取模的问题，由于一个比mod大的数，对mod进行取模运算才有取模的必要性，这样看来其实应该就是题目给出的提示，因为没有任何的数据还会超过这个范围，所以，我们只需要按照这个数据的范围来定义数据类型即可（如果不按这个范围，会WA），即unsigned long long或者unsigned \_\_int 64。

解题思路如图：

![Image 1][]![Image 1][]

解题思路：

设T(n)为该n边形（结点编号为1到n）所有可能的划分数，且设E(I,j)为i号结点和j号结点所连成的边。

则E(1,n)为多边形的其中一条边，那么，这条边要么是三角形的一条边，要么是四边形的一条边。

1. 如果E(1,n)为三角形的一条边，则设必定存在一个结点i(2<=i<=n-1),连同1结点和n结点一起组成一个三角形，那么这个三角形就把这个多边形分成了两部分，分别是一个i边形和一个(n-i+1)边形，那么此时，该多边形所有的划分数为：

![Image 1][]

2. 如果E(1,n)为四边形的一条边，则设必定存在一个结点i(2<=i<=n-2)(左半边结点)和一个结点j(i+1<=j<=n-1)(右半边结点),连同1结点和n结点一起组成一个四边形，那么这个四边形就把这个多边形分成了三部分，分别是一个i边形和一个(n-j+1)边形还有一个(j-i+1)边形，那么此时，该多边形所有的划分数为：

![Image 1][]

那么，多边形的总划分数T(n)=tmp1+tmp2 ;但是由于这样计算复杂度为O(n^3)仍然不能用算法实现，所以，采用一个技巧，设

![Image 1][]

那么，则有：

![Image 1][]

那么，则有：

![Image 1][]

即为代码实现的最终结果，复杂度为O(n^2)。

![Center][]

![Center 1][]

代码实现：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    typedef unsigned long long ULL;
    
    const int maxn=5100;
    
    ULL U[maxn],T[maxn];
    
    void unit()
    {
        memset(U,0,sizeof(U));
        T[2]=1;///通过计算前三项可以推得一个必须初始化的值
        for(int k=3;k<=5000;k++)
        {
            for(int i=2;i<=k-1;i++)
            {
                U[k]+=T[i]*T[k-i+1];
            }
            T[k]=U[k];
            for(int i=2;i<=k-2;i++)
            {
                T[k]+=T[i]*U[k-i+1];
            }
        }
    }
    
    int main()
    {
        long long n;
        unit();
        while(scanf("%lld",&n)!=EOF)
        {
            printf("%I64u\n",T[n]);
        }
        return 0;
    }

[http_poj.org_problem_id_3597]: http://poj.org/problem?id=3597
[3597_1.png]: http://poj.org/images/3597_1.png
[Image 1]: 
[Center]: /images/20220716/de6a4185a24146ce8422d73280680f7d.png
[Center 1]: /images/20220716/bcceb2f4c4344bb08cc2148ca5069af7.png