【区间DP】等腰三角形

动态规划DP

传送阵：CodeVS2186

思路：记$f_{i,j,k}$为第i到j个点连接恰好有k个等腰三角形的种数，区间dp，注意等腰三角形的几种情况。

代码比较清晰：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define mo 9397
int n,m,f[100][100][100];
int main(){
	while (~scanf("%d%d",&n,&m)){
		memset(f,0,sizeof f);
		for (int i=1;i<=n;i++) f[i][i+2][1]=f[i][i+1][0]=1;
		for (int i=3;i<=n-1;i++)
			for (int j=1;j<=n-i;j++)
				for (int k=1;k<=m;k++)
					for (int l=j+1;l<j+i;l++){
						int tt=0,s1,s2,s3;
						s1=n-(j+i)+j;
						s2=l-j;
						s3=j+i-l;
						if (s1==s2 || s2==s3 || s3==s1) tt=1;
						for (int r=0;r<=k-tt;r++)
							f[j][j+i][k]=(f[j][j+i][k]+f[j][l][r]*f[l][j+i][k-r-tt])%mo;
					}
		
		printf("%d\n",f[1][n][m]);
	}
	return 0;
}