hdu5115 区间dp

本文主要是介绍hdu5115 区间dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

和北京的那道题好像，可惜还是没能在比赛中做出来。

这个题目可以这样，将n个人分配到座位上，就是求1~n的全排列中符合题意的个数，其中1~n的编号就是他们坐的顺序，先枚举最后一个坐的人的座位编号，然后剩余的人（即编号）分成两部分，一部分在第一个人的左边，一个人在第一个人的右边，这样对于左右两边又是一次全新的分配（左右两边分配到的的编号可能不连续，但是他们有先后顺序即可确定坐的次序，无非是左边坐完右边坐），重复上述过程，直至只剩一个座位，此时方案数为1。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define delf int m=(l+r)>>1
#define ll long long intusing namespace std;int n;
int a[110];
ll dp[110][110];
ll c[110][110];
const int MOD=1000000000+7;void init()
{c[0][0]=1;for (int i=1;i<=100;i++){c[i][0]=c[i][i]=1;for (int t=1;t<i;t++)c[i][t]=(c[i-1][t-1]+c[i-1][t])%MOD;}return ;
}ll solve(int l,int r)
{if (dp[l][r]!=0)return dp[l][r];if (l==r)return 1;dp[l][r]=(solve(l,r-1)+solve(l+1,r))%MOD;for (int i=l+1;i<=r-1;i++){if (a[i-1]==a[i+1])     //当前最后一个坐的是第i个人，此时左右两端已经坐满//至于为什么要乘组合数，是因为总共r-l+1个人，其中第i个人已经分配，那么将剩余的人分成两拨，一拨左边一拨右边，//然后进入两边子程序，对左边来讲，左边是已经确定哪些人分配到左边之后的情况数，右边一样，，这样对于已经确定的//r-l+1个人，由于最后一个人的位置不一样，这样分配的到的方案肯定是不一样的。dp[l][r]=(dp[l][r]+(((solve(l,i-1)*solve(i+1,r))%MOD)*c[r-l][i-l])%MOD)%MOD;}return dp[l][r];
}int main()
{init();while (~scanf("%d",&n)){for (int i=1;i<=n;i++)scanf("%d",&a[i]);memset(dp,0,sizeof(dp));ll ans=solve(1,n);printf("%I64d\n",ans);}
}

这篇关于hdu5115 区间dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---