首页 > ACM题库 > HDU-杭电 > HDU 4175-Class Schedule-动态规划-[解题报告]HOJ
2015
05-23

HDU 4175-Class Schedule-动态规划-[解题报告]HOJ

Class Schedule

问题描述 :

At Fred Hacker’s school, there are T × C classes, divided into C catagories of T classes each. The day begins with all the category 1 classes being taught simultaneously. These all end at the same time, and then all the category 2 classes are taught, etc. Fred has to take exactly one class in each category. His goal is to choose the set of classes that will minimize the amount of "energy” required to carry out his daily schedule.
The energy requirement of a schedule is the sum of the energy requirement of the classes themselves, and energy consumed by moving from one class to the next through the schedule.

More specifically, taking the jth class in the ith category uses Eij units of energy. The rooms where classes take place are located at integer positions (ranging from 0 to L) along a single hallway. The jth class in the ith category is located at position Pij. Fred starts the day at position 0, moves from class to class, according to his chosen schedule, and finally exits at location L. Moving a distance d uses d units of energy.

输入:

The first line of the input is Z ≤ 20 the number of test cases. This is followed by Z test cases. Each test case begins with three space-separated integers: C, T, and L. Each of the following C× T lines gives, respectively, the location and energy consumption of a class. The first T lines represent the classes of category 1, the next T lines represent the classes of category 2, and so on. No two classes in the same category will have the same location.

Bounds:
1 ≤ C ≤ 25
1 ≤ T ≤ 1000
1 ≤ L ≤ 1,000,000
1 ≤ Eij ≤ 1,000,000
0 ≤ Pij ≤ L

输出:

The first line of the input is Z ≤ 20 the number of test cases. This is followed by Z test cases. Each test case begins with three space-separated integers: C, T, and L. Each of the following C× T lines gives, respectively, the location and energy consumption of a class. The first T lines represent the classes of category 1, the next T lines represent the classes of category 2, and so on. No two classes in the same category will have the same location.

Bounds:
1 ≤ C ≤ 25
1 ≤ T ≤ 1000
1 ≤ L ≤ 1,000,000
1 ≤ Eij ≤ 1,000,000
0 ≤ Pij ≤ L

样例输入:

1
3 2 5
2 1
3 1
4 1
1 3
1 4
3 2

样例输出:

11

Hint
Explanation of Sample Input: Fred must take 3 classes every day, and for each he has 2 choices. The hall has length 5. His first possible class is located at position 2 and will take 1 unit of energy each day, etc. Explanation of Sample Output: Here is one way to obtain the minimum energy: Go to the class at location 2. Energy used: 3 Next, go to the class at location 4. Energy used: 6 Then go to the class at location 3. Energy used: 9 Finally, leave the school at location 5. Energy used: 11

题意:有c个时段的课,每个时段有t种课,每种课对应一个能量消耗值,从一节课转移到另一节课移动的距离为n,则移动消耗的能量也是n,现在小明要上课,他全时段的课都要上,同一时段只能选一种课,并且一天结束之后还要赶到L的位置,求他的最小能量消耗。

分析:

数塔模型,从后往前推;三重循环。20*25*1000*1000不会超时(20是tests)。为什么是数塔模型呢,因为分成了c段,每段必须选且只能选一个,依照段的顺序走到终点。

状态:dp[i][j]表示第i时段上第j节课的最优解;转移:dp[i][k]=min(dp[i][k],dp[i+1][j]+a[i][j].y+abs(a[i+1][j].x-a[i][k].x)

这题很简单,稍微一想就出来了,但是比赛的时候默认很难,连题都没静下心来仔细读。要相信自己,不要急,怕什么呢。

代码:

#include<cstdio>
#include<cmath>
#define min(a,b) a<b?a:b
#define INF 1000000007
using namespace std;
int z;
int c,t,l;
int dp[100][1005];
struct node{
	int x,y;
}a[100][1005];
int main()
{
	scanf("%d",&z);
	while(z--){
		scanf("%d%d%d",&c,&t,&l);
		for(int i=1;i<=c;i++){
			for(int j=1;j<=t;j++) scanf("%d%d",&a[i][j].x,&a[i][j].y);
		}
		
		for(int i=0;i<=c;i++)
		   for(int j=0;j<=t;j++) 
		      dp[i][j]=INF;
		      
		for(int i=1;i<=t;i++) dp[c][i]=a[c][i].y+l-a[c][i].x;
		for(int i=c-1;i>0;i--){
			for(int k=1;k<=t;k++){
				for(int j=1;j<=t;j++){
				   dp[i][k]=min(dp[i][k],dp[i+1][j]+a[i][k].y+abs(a[i+1][j].x-a[i][k].x));
			    }
			}			
		}
		int ans=INF;
		for(int i=1;i<=t;i++) 
		   ans=min(ans,dp[1][i]+a[1][i].x);
		printf("%d\n",ans);
	}
}

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

参考:http://blog.csdn.net/ac_0_summer/article/details/47113891