UVa12875 - Concert Tour(DP、DAG)

題目大意

有一位歌手要舉辦演唱會，在各縣市中的百貨公司進行演唱，來吸引更多的顧客消費，給你 c 天、有許多個百貨公司必須要去，給你在每一天每一個百貨公司演唱預期帶來的利益，以及每一個百貨公司到另一個百貨公司的成本，請告訴我最大化利益為多少
題目連結

重點觀念

演算法知識 - Directed Acyclic Graph by 大衛的筆記

分析

• 根據重點觀念，因為可以有多個起點，因此使用 DP
• 因此使用三迴圈，從第幾天開始，再從 a 到 b 點，轉移方程式為 dp[第i+1天][抵達 k 百貨公司], dp[第 i 天][抵達 j 百貨公司] + profit[第 k 天][在 i+1 百貨公司] - cost[從 j 百貨公司][到 k 百貨公司]

參考連結

UVa 12875 - Concert Tour by morris

心得

好久沒寫 DAG，都有點忘記要怎麼寫了QQ。
一開始還想把它寫成 DFS

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 200
using namespace std;
int t, s, c;
int dp[MAXN][MAXN], cost[MAXN][MAXN], profit[MAXN][MAXN]; //dp, cost 百貨公司移動成本, 百貨公司演唱利益

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> s >> c;
        for(int i = 1; i <= s; i++){
            for(int j = 1; j <= c; j++){
                cin >> profit[i][j];
            }
        }
        for(int i = 1; i <= s; i++){
            for(int j = 1; j <= s; j++){
                cin >> cost[i][j];
            }
        }

        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < c; i++){ //第幾天
            for(int j = 1; j <= s; j++){ //從 j 百貨公司
                for(int k = 1; k <= s; k++){ //到 k 百貨公司
                    dp[i+1][k] = max(dp[i+1][k], dp[i][j] + profit[k][i+1] - cost[j][k]);
                }
            }
        }
        int ans = 0;
        for(int i = 1; i <= s; i++){ //尋找最大利益
            ans = max(ans, dp[c][i]);
        }
        cout << ans << "\n";
    }
    return 0;
}