首页 > ACM题库 > HDU-杭电 > hdu 2372 El Dorado-动态规划[解题报告]C++
2014
01-05

hdu 2372 El Dorado-动态规划[解题报告]C++

El Dorado

问题描述 :

Bruce Force has gone to Las Vegas, the El Dorado for gamblers. He is interested especially in one betting game, where a machine forms a sequence of n numbers by drawing random numbers. Each player should estimate beforehand, how many increasing subsequences of length k will exist in the sequence of numbers.

Bruce doesn’t trust the Casino to count the number of increasing subsequences of length k correctly. He has asked you if you can solve this problem for him.

输入:

The input contains several test cases. The first line of each test case contains two numbers n and k (1 ≤ k ≤ n ≤ 100), where n is the length of the sequence drawn by the machine, and k is the desired length of the increasing subsequences. The following line contains n pairwise distinct integers ai (-10000 ≤ ai ≤ 10000 ), where ai is the ith number in the sequence drawn by the machine.

The last test case is followed by a line containing two zeros.

输出:

The input contains several test cases. The first line of each test case contains two numbers n and k (1 ≤ k ≤ n ≤ 100), where n is the length of the sequence drawn by the machine, and k is the desired length of the increasing subsequences. The following line contains n pairwise distinct integers ai (-10000 ≤ ai ≤ 10000 ), where ai is the ith number in the sequence drawn by the machine.

The last test case is followed by a line containing two zeros.

样例输入:

10 5
1 2 3 4 5 6 7 8 9 10
3 2
3 2 1
0 0

样例输出:

252
0


昨天热身赛遇到一题不会写,今天问了下是个dp的问题,但是经过思索后得到一个新的算法,这个方法做最大上升子序列还行吧,但是由于数据太大,根本无法用上组合思想,果断的错误了,哥的人生就是以个悲剧,最后跑去网上搜别人的解题报告,结果只有个代码,只能自行参悟,看完后终于有知道了怎么把dp以前的状态和当前状态联系起来,本人总结的状态方程是dp[i][j]=sum{ 当a[i]>a[k]时(k 其中dp[i][j]表示从首字符到i字符时长度为j的上升子串的数量,知道这个就很好做了。
百度后终于找到了题目网址http://acm.hdu.edu.cn/showproblem.php?pid=2372
写完后提交错了蛋疼了一个下午,终于知道了原因,因为我们学校用的是longlong和它的编译器不符,改用__int64后就过了,下面是这题和我的代码。

#include<stdio.h>
int main()
{
	while(1)
	{
		__int64 dp[105][105]={0};__int64 l;
		int n,m,i,j,k,a[105];
		
		scanf("%d %d",&n,&m);
		if(n==0&&m==0)
			return 0;
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
		}
		for(i=1;i<=n;i++)
		{
			dp[i][1]=1;
		}
		for(i=2;i<=n;i++)//这里开始dp
		{
			for(j=2;j<=m;j++)
			{
				for(k=1;k<i;k++)
				{
					if(a[i]>a[k])
					{
						dp[i][j]+=dp[k][j-1];
					}
				}
			}
		}
		l=0;
		for(i=m;i<=n;i++)//将长度为m的所有值相加就是结果了
		{
			l+=dp[i][m];
		}
		printf("%I64d/n",l);
	}
	return 0;
}

 


  1. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。