首页 > ACM题库 > HDU-杭电 > HDU 3933-Dark Parth-动态规划-[解题报告]HOJ
2015
04-14

HDU 3933-Dark Parth-动态规划-[解题报告]HOJ

Dark Parth

问题描述 :

In the dark path, the single figure is walking difficultly in the listless rainfall. No one knows his real destination.

‘Young, have you ever tasted the loneliness walking in dark path; have you ever run about madly just to avoid the pain in the deep heart?’
After BiYao’s death, XiaoFan changed to GuiLi .Running in such darkness, leaving the rain wet out his clothes, leaving the darkness cover up his eyes, he will never regret!

Now, we separate the path into n parts with the same length (1<=N<=1000).Every part has its value Ai (-1000<=Ai<=1000). If Xiaofan walks through the ith part of the path, he will get the hurt Ai. His trump ShaoHuoGun will give him S chances to fly (1<=S<=100). Every chance can help him get through one part of the path without any hurt. But there’s a limit: The length of his fly Si should be longer than La and shorter than Lb (1<=La<=Si<=Lb<=n).
Your job is to find the best way for XiaoFan to have the least hurt.
Hit: Two different fly paths can’t cover each other, and times of fly can be fewer than the given times S.

输入:

There are several test cases. The first line is an integer N, then the second line have three integers Lb, La, S, then followed N integers A1.A2…An.The test end by n = 0.

输出:

There are several test cases. The first line is an integer N, then the second line have three integers Lb, La, S, then followed N integers A1.A2…An.The test end by n = 0.

样例输入:

10
3 2 3
3 1 -5 -9 2 -1 1 -7 9 10

10
4 3 4
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

0

样例输出:

-21
-10

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

题目意思:一条路分成n段,每段都有一个悲伤值,X决定走完这段路,但想尽可能的少得悲伤值,在这段路的行走过程中他有s次飞行的机会,飞行时不得到悲伤值,但是飞行的长度必须大于la且小于lb,求X走完这段路的最小悲伤值。


典型的DP问题。dp[i][j]表示前j段路总共飞行了i次获得的最小悲伤值,状态转移方程:dp[i][j]=min(dp[i][j],dp[i-1][j-k]);

代码如下:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cctype>

using namespace std;

const int maxn=1001;
const int maxs=101;

int dp[maxs][maxn];
int data[maxn];

int min(int a,int b){
	return a<b?a:b;
}

int main(){
	int n,s,la,lb;
	while(scanf("%d",&n)&&n){
		scanf("%d%d%d",&lb,&la,&s);
		memset(dp,0,sizeof(dp));
		int i,j,k;
		for(i=1;i<=n;i++){
			scanf("%d",&data[i]);//
            dp[0][i]=data[i];
			dp[0][i]+=dp[0][i-1];//当使用0次飞行特权时走过i段的悲伤值为1到i段悲伤值的和
		}
		for(i=1;i<=s;i++){
			for(j=1;j<=n;j++){
				dp[i][j]=dp[i][j-1]+data[j];//首先让dp[i][j]=dp[i][j-1],当然这里也可以放在下面的选小值的函数中
				for(k=la;k<=lb && k<=j;k++){
					dp[i][j]=min(dp[i][j],dp[i-1][j-k]);//状态转移 很好理解
				}
			}
		}
		int ans=1<<30;
		for(i=0;i<=s;i++){
			ans=min(dp[s][n],ans);//n段都走完选悲伤值最小的
		}
		printf("%d\n",ans);
	}
	return 0;
}


版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/iaccepted/article/details/6742975


  1. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。