POJ 3230 Travel：動態規劃求旅行最大收益

問題描述

旅行者在 n 個城市間移動，共 m 天。每天可選擇留在原城或移動到另一城市，移動/停留需支付費用 mat[i][j]（i==j 表示停留費用）。第 i 天在第 j 城市可獲得收益 w[i][j]。初始位於城市 1。求最大總收益（收益 - 支出）。

動態規劃建模

定義 dp[i][j]：前 i 天結束時位於城市 j 的最大淨收益。
轉移方程：

dp[i][j] = max_{k=1..n} ( dp[i-1][k] - mat[k][j] + w[i][j] )

初始條件：dp[0][1] = 0，其餘 -INF。
第 1 天特別處理：dp[1][i] = dp[0][1] - mat[1][i]（尚未獲得收益）。
最終答案：max_{j=1..n} dp[m][j]。

複雜度

• 狀態數：O(m·n)；
• 轉移：O(n)；
• 總計 O(m·n²)，n,m < 100 時 10⁶ 量級，輕鬆通過。

參考代碼（C++11）

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int dp[105][105], mat[105][105], w[105][105];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m) {
        if (!n && !m) break;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                cin >> mat[i][j];
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                cin >> w[i][j];

        memset(dp, -0x3f, sizeof(dp));
        dp[0][1] = 0;
        for (int i = 1; i <= n; ++i) dp[1][i] = dp[0][1] - mat[1][i];

        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                for (int k = 1; k <= n; ++k)
                    dp[i][j] = max(dp[i][j], dp[i-1][k] - mat[k][j] + w[i][j]);

        int ans = 0;
        for (int i = 1; i <= n; ++i) ans = max(ans, dp[m][i]);
        cout << ans << '\n';
    }
    return 0;
}

優化提示

若 n 較大，可利用矩陣乘法（最大加法半環）將轉移加速至 O(n³ log m)，但本題數據範圍下朴素 DP 即可。