解題區/解題區 - UVa

UVa 12875 - Concert Tour

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

現在有位歌手，要舉辦演唱會，在各地的百貨公司打算邀請歌手來演唱，藉以吸引更多的顧客來消費。每個百貨公司提供在哪一天歌手來演唱時可以得到的獲益，歌手必須自費從另一個地點到另一個地點，因此會給定兩地之間的自費費用。可以留在原地。

求歌手在 m 天內可以獲得的最大利益為何，假設第一天到任何場地都是 0 花費，沒有指派最後一天所在的位置。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
3
3 4
1 3 20 40
50 20 1 2
20 50 50 1
0 10 10
10 0 10
10 10 0
3 3
20 20 20
20 20 20
20 20 20
0 20 40
20 0 40
40 10 0
2 4
10 20 10 20
20 10 20 10
0 5
5 0

Sample Output

1
2
3
170
60
65

Solution

定義狀態 dp[stores][days]，在第幾天到哪一個城鎮。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 128
#define MAXM 64
long long dp[MAXN][MAXM];
int profit[MAXN][MAXM], cost[MAXN][MAXN];
int main() {
    int testcase, n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                scanf("%d", &profit[i][j]);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &cost[i][j]);
                
        memset(dp, 0, sizeof(dp));
        
        long long ret = 0;
        for (int i = 0; i < n; i++)
            dp[i][0] = profit[i][0];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    dp[k][i+1] = max(dp[k][i+1], dp[j][i] + profit[k][i+1] - cost[j][k]);
                }
            }
        }
        for (int i = 0; i < n; i++)
            ret = max(ret, dp[i][m-1]);
        printf("%lld\n", ret);
    }
    return 0;
}