净月潭航线

2018-08-21

字数统计: 369字 | 阅读时长: 1min

##【问题描述】
净月潭国家森林公园是吉林省著名的5A级景区，因为公园中有一深潭而命名，这个深潭是圆形的，吉林省的OIER们要在圆潭的边上建N个码头，用以建立航线（可能为0条航线），航线只能是一个码头到另一个码头，并且多条航线之间不能相交，共用码头也算相交。请OIER们算一下，共有多少建立航线的方案？

##【输入格式】

从文件route.in中输入数据。

一行一个数N

##【输出格式】

输出到文件route.out中。

由于结果可能很大，你只需要输出这个答案mod 12345的值。

##【样例输入】

##【样例输出】

##【数据规模与约定】

对于30%数据：N ≤ 10

对于50%数据：N ≤ 100

对于100%数据：N ≤ 1000

#include<bits/stdc++.h>
using namespace std;
int f[10000];
int main()
{
	int n;
	scanf("%d",&n);
	f[0]=f[1]=1;
	for(int i=2;i<=n;i++)
	{
		f[i]=f[i-1];
		for(int j=2;j<=i;j++)
		(f[i]+=f[j-2]*f[i-j])%=12345;
	}
	printf("%d",f[n]);
	return 0;
}

题解：

f[n]记录答案，每一个f[n]可继承上一个f[n-1]的答案。然后考虑新增的点，选择一个点与之连线，将图分为两个部分，两部分点数的f[n]相乘便为连该条线的情况数。枚举两边的点数，更新答案。

本文作者： syrsteven
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/bde3d801.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！