宁波市第31届中小学程序设计比赛模拟试题【动态规划】cirs

素颜马尾好姑娘i 2022-06-10 23:39 107阅读 0赞

题目描述  
  
Czyzoiers 都想知道小 x 为什么对鸡蛋饼情有独钟。经过一番逼问，小 x 道出了实情：因为他喜欢圆。最近小 x 又发现了一个关于圆的有趣的问题：在圆上有2N 个不同的点，小 x 想用 N 条线段把这些点连接起来（每个点只能连一条线段），使所有的线段都不想交，他想知道这样的连接方案有多少种？  
  
输入  
  
有且仅有一个正整数 N（N≤3000）。  
  
输出  
  
要求的方案数（结果 mod 100000007）。  
  
样例输入  
2  
  
  
样例输出  
5  
  
  
提示  
  
  
1 号点与 2 号点连接：2 种。  
1 号点与 4 号点连接：1 种。  
1 号点与 6 号点连接：2 种。  
![Center][]  
![Image 1][]

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    #include <map>
    #include <string>
    #include <stack>
    #define LL long long
    #define INF 0x7fffffff
    #define mod 100000007
    #define PI 3.1415926535897932
    #define E 2.718281828459045
    using namespace std;
    int n;
    LL a[3005];
    int main()
    {
        scanf("%d",&n);
        memset(a,0,sizeof(a));
        a[0]=1;
        for(int i=1;i<=n;i++)
            for(int j=0;j<=i-1;j++)
            a[i]=(a[i]+a[j]*a[i-j-1]) % mod;
        printf("%lld",a[n]);
    
    
        return 0;
    }

[Center]: /images/20220611/56f023c9268c4c10bb8b3da7759c3bc8.png
[Image 1]: