题目描述：给定一个正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（n2k2），可以过。
如果不大理解的话，可以结合凸多边形三角划分这道题想一想。
看一下代码。
#include#include #include #include #include #include #include #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 = 10005;const ll INF = 1000000009;const int mod = 9397;int read(){ int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op;}int n,k,dp[105][105];bool judge(int x,int m){ int ta = min(x - 1,n - x + 1),tb = min(m - 1,n - m + 1),tc = min(m - x,n - m + x); return (ta == tb || tb == tc || ta == tc);}int dfs(int n,int k){ if(dp[n][k] != -1) return dp[n][k]; if(n <= 2) return 0; int cur = 0; rep(x,2,n-1) { rep(j,0,k-judge(x,n)) cur += dfs(x,j) * dfs(n-x+1,k-j-judge(x,n)),cur %= mod; } return dp[n][k] = cur;}int main(){ n = read(),k = read(); memset(dp,-1,sizeof(dp)); dp[2][0] = 1; printf("%d\n",dfs(n,k)); return 0;}