首页 > ACM题库 > HDU-杭电 > HDU 2861-Stools-动态规划-[解题报告]HOJ
2014
02-17

HDU 2861-Stools-动态规划-[解题报告]HOJ

Stools

问题描述 :

Patti and Terri run a bar in which there are 15 stools. One day, Darrell entered the bar and found that the situation how customers chose the stools were as follows:
OOEOOOOEEEOOOEO
O means that the stool in a certain position is used, while E means that the stool in a certain position is empty (here what we care is not who sits on the stool, but whether the stool is empty).As the example we show above, we can say the situation how the 15 stools is used determines 7 intervals (as following):
OO E OOOO EEE OOO E O

Now we postulate that there are N stools and M customers, which make up K intervals. How many arrangements do you think will satisfy the condition?

输入:

There are multi test cases and for each test case:
Each case contains three integers N (0<N<=200), M (M<=N), K (K<=20).

输出:

There are multi test cases and for each test case:
Each case contains three integers N (0<N<=200), M (M<=N), K (K<=20).

样例输入:

3 1 3
4 2 4

样例输出:

1
2

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2861

题意就是n个板凳有m个人坐,求刚好将序列分成k段的方式,用dp[i][j][k][0]和dp[i][j][k][1]记录最后一根板凳没有人和有人的方法数依次递推。开始看到这道题的时候以为要推组合学公式,后来听学长讲才知道只是一个递推而已,所以以后一定要多注意数据范围,以免偏离思考方向。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 110
int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
__int64 dp[220][220][22][2];
int n,m,k;
void init()
{
    int i,j,k;
    memset(dp,0,sizeof(dp));
    dp[1][1][1][1]=1;
    dp[1][0][1][0]=1;
    for(i=1;i<201;i++)
        dp[i][0][1][0]=1;
    for(i=2;i<201;i++)
        for(j=1;j<=i;j++)
            for(k=1;k<=20&&k<=i;k++)
            {
                dp[i][j][k][0]=dp[i-1][j][k][0]+dp[i-1][j][k-1][1];
                dp[i][j][k][1]=dp[i-1][j-1][k][1]+dp[i-1][j-1][k-1][0];
            }
}
int main()
{
    init();
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        printf("%I64d\n",dp[n][m][k][0]+dp[n][m][k][1]);
    }
}

解题参考:http://blog.csdn.net/wings_of_liberty/article/details/7361536


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  3. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。

  4. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。