首页 > ACM题库 > HDU-杭电 > HDU 1580 Always On the Run-动态规划-[解题报告] C++
2013
12-12

HDU 1580 Always On the Run-动态规划-[解题报告] C++

Always On the Run

问题描述 :

Screeching tires. Searching lights. Wailing sirens. Police cars everywhere. Trisha Quickfinger did it again! Stealing the `Mona Lisa’ had been more difficult than planned, but being the world’s best art thief means expecting the unexpected. So here she is, the wrapped frame tucked firmly under her arm, running to catch the northbound metro to Charles-de-Gaulle airport.

But even more important than actually stealing the painting is to shake off the police that will soon be following her. Trisha’s plan is simple: for several days she will be flying from one city to another, making one flight per day. When she is reasonably sure that the police has lost her trail, she will fly to Atlanta and meet her `customer’ (known only as Mr. P.) to deliver the painting.

Her plan is complicated by the fact that nowadays, even when you are stealing expensive art, you have to watch your spending budget. Trisha therefore wants to spend the least money possible on her escape flights. This is not easy, since airlines prices and flight availability vary from day to day. The price and availability of an airline connection depends on the two cities involved and the day of travel. Every pair of cities has a `flight schedule’ which repeats every few days. The length of the period may be different for each pair of cities and for each direction.

Although Trisha is a good at stealing paintings, she easily gets confused when booking airline flights. This is where you come in.

输入:

The input contains the descriptions of several scenarios in which Trisha tries to escape. Every description starts with a line containing two integers n and k. n is the number of cities through which Trisha’s escape may take her, and k is the number of flights she will take. The cities are numbered 1, 2, …, n, where 1 is Paris, her starting point, and n is Atlanta, her final destination. The numbers will satisfy 2 <= n <= 10 and 1 <= k <= 1000.
Next you are given n(n – 1) flight schedules, one per line, describing the connection between every possible pair of cities. The first n – 1 flight schedules correspond to the flights from city 1 to all other cities (2, 3, …, n), the next n – 1 lines to those from city 2 to all others (1, 3, 4, …, n), and so on.

The description of the flight schedule itself starts with an integer d, the length of the period in days, with 1 <= d <= 30. Following this are d non-negative integers, representing the cost of the flight between the two cities on days 1, 2, …, d. A cost of 0 means that there is no flight between the two cities on that day.

So, for example, the flight schedule “3 75 0 80” means that on the first day the flight costs 75, on the second day there is no flight, on the third day it costs 80, and then the cycle repeats: on the fourth day the flight costs 75, there is no flight on the fifth day, etc.

The input is terminated by a scenario having n = k = 0.

输出:

For each scenario in the input, first output the number of the scenario, as shown in the sample output. If it is possible for Trisha to travel k days, starting in city 1, each day flying to a different city than the day before, and finally (after k days) arriving in city n, then print “The best flight costs x.”, where x is the least amount that the k flights can cost.

If it is not possible to travel in such a way, print “No flight possible.”.

Print a blank line after each scenario.

样例输入:

3 6
2 130 150
3 75 0 80
7 120 110 0 100 110 120 0
4 60 70 60 50
3 0 135 140
2 70 80
2 3
2 0 70
1 80
0 0

样例输出:

Scenario #1
The best flight costs 460.

Scenario #2
No flight possible.

题意:给你n个城市,k天时间,要你第k天到n城,难懂的题意啊,还是看了别人的解释,注意price[j][i][x]代表的是从j到i的第x天的价格,是从第一天就开始循环的,从一个城市到达一个城市默认是一天,状态转移方程倒是不难推。dp[i][j]代表第j天到i城价格最小,那么dp[i][j] = min(dp[i][j],dp[d][j-1]+price[d][i][x]),dp[1][0] = 0;

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 1<<29;

int day[15][15],price[15][15][35];
int dp[15][1005];

int main(){
    int n,k;
    int t = 0;
    while (scanf("%d%d",&n,&k) != EOF && n+k){
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++){
                if (i != j){
                    scanf("%d",&day[i][j]);
                    for (int l = 1; l <= day[i][j]; l++)
                        scanf("%d",&price[i][j][l]);
                }
            }
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= k; j++)
                dp[i][j] = INF;

        dp[1][0] = 0;

        for (int i = 1; i <= k; i++)
            for (int j = 1; j <= n; j++)
                for (int l = 1; l <= n; l++)
                    if (j != l){
                        int a = (i - 1) % day[l][j] + 1;  // 看看是坐第几趟的
                        if (price[l][j][a] && dp[l][i-1] != INF)
                            dp[j][i] = min(dp[j][i],dp[l][i-1] + price[l][j][a]);
                    }
        printf("Scenario #%d\n", ++t);
        if (dp[n][k] != INF)
            printf("The best flight costs %d.\n\n", dp[n][k]);
        else printf("No flight possible.\n\n");
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/u011345136/article/details/11785727


  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  3. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  4. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法