本文主要是介绍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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!