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

hdu 2363 Cycling-动态规划-[解题报告]C++

Cycling

问题描述 :

You want to cycle to a programming contest. The shortest route to the contest might be over the tops of some mountains and through some valleys. From past experience you know that you perform badly in programming contests after experiencing large differences in altitude. Therefore you decide to take the route that minimizes the altitude difference, where the altitude difference of a route is the difference between the maximum and the minimum height on the route. Your job is to write a program that finds this route.
You are given:

the number of crossings and their altitudes, and

the roads by which these crossings are connected.
Your program must find the route that minimizes the altitude difference between the highest and the lowest point on the route. If there are multiple possibilities, choose the shortest one.
For example:

In this case the shortest path from 1 to 7 would be through 2, 3 and 4, but the altitude difference of that path is 8. So, you prefer to go through 5, 6 and 4 for an altitude difference of 2. (Note that going from 6 directly to 7 directly would have the same difference in altitude, but the path would be longer!)

输入:

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with two integers n (1 <= n <= 100) and m (0 <= m <= 5000): the number of crossings and the number of roads. The crossings are numbered 1..n.

n lines with one integer hi (0 <= hi <= 1 000 000 000): the altitude of the i-th crossing.

m lines with three integers aj , bj (1 <= aj , bj <= n) and cj (1 <= cj <= 1 000 000): this indicates that there is a two-way road between crossings aj and bj of length cj . You may assume that the altitude on a road between two crossings changes linearly.
You start at crossing 1 and the contest is at crossing n. It is guaranteed that it is possible to reach the programming contest from your home.

输出:

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with two integers n (1 <= n <= 100) and m (0 <= m <= 5000): the number of crossings and the number of roads. The crossings are numbered 1..n.

n lines with one integer hi (0 <= hi <= 1 000 000 000): the altitude of the i-th crossing.

m lines with three integers aj , bj (1 <= aj , bj <= n) and cj (1 <= cj <= 1 000 000): this indicates that there is a two-way road between crossings aj and bj of length cj . You may assume that the altitude on a road between two crossings changes linearly.
You start at crossing 1 and the contest is at crossing n. It is guaranteed that it is possible to reach the programming contest from your home.

样例输入:

1
7 9
4
9
1
3
3
5
4
1 2 1
2 3 1
3 4 1
4 7 1
1 5 4
5 6 4
6 7 4
5 3 2
6 4 2

样例输出:

2 11

dp题,用dp[i][j][k]表示 剩下i头牛 头牛的体力为j 已经跑了k圈 所用的最短时间

尽量把头牛的体力用完后dropout再换牛,否则会多消耗总体力;头牛没有体力之后就可以直接dropout换牛,接上来的牛的体力等于e-k

#include <cstdio>

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

const int INF = 0x3f3f3f3f;
int n,e,d,ans;
int dp[21][101][101];

int main()
{
	while (scanf("%d%d%d",&n,&e,&d)==3)
	{
		ans=INF;
		for (int i=0;i<=n;i++)
			for (int j=0;j<=e;j++)
				for (int k=0;k<=d;k++)
					dp[i][j][k]=INF;
		dp[n][e][0]=0;
		for (int k=0;k<=d;k++)
			for (int i=n;i>=1;i--)
				for (int j=e;j>=0;j--)
				{
					if (dp[i][j][k]==INF) continue;
					if (k==d) ans=Min(ans,dp[i][j][k]);
					for (int x=1;x+k<=d;x++)
					{
						if (j>=x*x)
							dp[i][j-x*x][k+x]=Min(dp[i][j-x*x][k+x],dp[i][j][k]+1);
						if (i>=2 && e-k-x*x>=0)
							dp[i-1][e-k-x*x][k+x]=Min(dp[i-1][e-k-x*x][k+x],dp[i][j][k]+1);
					}
				}
		if (ans==INF) puts("0");
		else printf("%d\n",ans);
	}
	return 0;
}

解题转自:http://blog.csdn.net/huangshenno1/article/details/8658786


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept