首页 > ACM题库 > HDU-杭电 > HDU 1424 Increasing Sequences-动态规划-[解题报告] C++
2013
12-10

HDU 1424 Increasing Sequences-动态规划-[解题报告] C++

Increasing Sequences

问题描述 :

This is a problem from ZOJ 1499.To make it easyer,you just need output the last number.If there are leading zeros you should delete it.

输入:

Input will consist of multiple test cases. Each case will consist of one line, containing a string of digits of maximum length 80. A line consisting of a single 0 terminates input.

输出:

For each instance,output the last number.

样例输入:

3456 
3546 
3526 
0001 
100000101

样例输出:

6
46
26
1
101

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1421

状态Dp[i][j]为前i件物品选j对的最优解
i=j*2,只有一种选择即 Dp[i-2][j-1]+(w[i]-w[i-1])^2

i>j*2,Dp[i][j] = min(Dp[i-1][j],Dp[i-2][j-1]+(w[j]-w[j-1])^2)

 

#include<cstdio>
#include<algorithm>
using namespace std;
#define min(x,y) (x)<(y)?(x):(y)
int a[2005];
int dp[2005][2005/2];
void work(int n,int k)
{
	int i,j;
	dp[0][0] = 0;//当取0件的时候所耗费的精力为0
	for(i = 2; i <= n; i++)
	{
		dp[i][0] = 0;
		for(j = 1; j <= i/2 ; j++)
			if(i -1 >= j*2)//当i-1>= j*2的时候
				dp[i][j] = min(dp[i-1][j],dp[i-2][j-1]+(a[i-1]-a[i])*(a[i-1]-a[i]));
			else//当i-1< j*2的时候
				dp[i][j] = dp[i-2][j-1] + (a[i-1]-a[i])*(a[i-1]-a[i]);
	}
	printf("%d\n",dp[n][k]);//输出最小的疲劳度。
}
int main()
{
	int n,k,i;
	while(~scanf("%d%d",&n,&k))
	{
		for(i = 1; i <= n; i++)//输入数据,输入从1开始。
			scanf("%d",a+i);
		sort(a+1,a+n+1);//将元素从小到大进行排序。
		work(n,k);
	}
	return 0;
}

 

解题报告转自:http://blog.csdn.net/luo964061873/article/details/7922889


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