首页 > ACM题库 > HDU-杭电 > HDU 1292 “下沙野骆驼”ACM夏令营-动态规划-[解题报告] C++
2013
12-04

HDU 1292 “下沙野骆驼”ACM夏令营-动态规划-[解题报告] C++

“下沙野骆驼”ACM夏令营

问题描述 :

大家都知道,杭电计算机学院为了吸引更多的学生参与到程序设计竞赛中去,从2005年秋天,开始举行月赛,并一直坚持到了现在。事实表明,这项措施的效果还是很明显的,现在坚持参加训练的学生比以前有了较大幅度的增长,整体水平也有了较大的提高。
为了更好的促进这项竞赛的发展,计算机学院又有了新的计划:准备在每年的暑假举行一个为期半个月的程序设计夏令营活动,活动的全称是“下沙野骆驼ACM夏令营”,准备邀请全球的编程高手共同训练,邀请对象当然少不了HFUT的DYGG,NIT的DGMM,ZJUT的QWDD,如果QH的LTC一定要来,我们也不会嫌弃,虽然他水平比其他人差了些,毕竟是杭州人,要给点面子的,再说,共同进步才是我们的最终目的,呵呵。
活动的安排初步定为7项内容,具体是:
1、第一天,倒时差(主要照顾欧美的选手)。
2、第二天,参观杭电校园,并在参观结束举行有奖竞答,偷偷透露一下,题目我已经设计好了:“杭电校院一共有几棵树?”(正确答案:3897棵),答对的营员奖励雪糕一支(不是哈根达斯,是杭州五丰生产的,民族工业还是要支持的)。
3、第三天,参观杭电ACMer的寝室,主要目的是让部分来自资本主义国家的选手看看我们是如何管理学生宿舍的,其中一项重要内容是向全球推广我校首创的“党员模范寝室”。
4、第四天,练习赛,题目只有一个:“非著名高校HD一共有教职工num个,分布在X个部门,假设每个部门有y1个正处级领导,y2个副处级领导,y3个付处级调研员,y4个正科级干部,y5个副科级干部,请输出HD的领导人员占教职工总数的比例,结果保留两位小数。”(告诉你,这个题目对于欧美选手来说有个陷阱,最后的结果可能大于100%!这是他们如何也想不到的:)
5、第五天~第十三天,算法交流,主要讨论如何求两个数的最小公倍数。
6、第十四天,自由组队(每队人数不限,呵呵,注意了),参加“下沙野骆驼杯”程序设计大赛,冠军将获得一匹下沙的野骆驼(我们主场不知道有没有机会…)
7、最后一天,篝火晚会,主题:“ACM,你到底爱不爱我?!”,主持人:骆驼王子和他一个普通老同学。

负责这次夏令营活动的是05级的小师弟Linle(一个打字速度很快,号称仅次于Fe(OH)2的小伙子),他很聪明,也很勤奋,现在他就在思考一个问题,如果一共来了n个同学,按照组队规则,一共会有多少种不同的组队方案呢?

输入:

输入数据的第一行是一个整数C(1<C<25),表示测试实例的数目,然后是C行数据,每行一个整数n(0<n<25),表示营员的人数。

输出:

对于每组输入数据,请输出组队的方案数目,每个测试实例占一行。

样例输入:

3
1
2
3

样例输出:

1
2
5

考虑一支队伍分组的数目,如果这支队伍有n个人,就有n种情况分别是一个组,两个组。。。。

i个人分成j组有两种方式,一种是i-1个人分成j-1组之后,第i个人独立分成一组,另一种情况是i-1个人分成j组,第i个人随便加入j组中的任何一组,也都符合条件。状态转移方程为f[i][j]=f[i-1][j-1]+f[i-1][j]*j。

#include <iostream>
#include <cstring>
using namespace std;
long long dp[30][30];
int main(int argc, char *argv[])
{
	int t,n,i,j;long long ans;
	cin>>t;
	while(t--)
	{
		cin>>n;
		dp[1][1]=1;
		for(i=2;i<=n;i++)
		for(j=1;j<=n;j++)
		dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*j;
		for(ans=0,i=1;i<=n;i++)
		ans+=dp[n][i];
		cout<<ans<<endl;
	}
	return 0;
}

 


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

  2. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  3. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  4. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。