您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

HDU 2452 Navy maneuvers 記憶化搜索博弈論

編輯：C++ 入門

HDU 2452 Navy maneuvers 題目解析

有向無環圖，兩船從入度 0 點出發，輪流移動。一船目標最小化終點值，另一船目標最大化。記憶化搜索：dp[i][0] 以 i 為起點最小值目標結果，dp[i][1] 最大值目標結果。枚舉所有入度 0 點作為起點，取最大值與閾值 f 比較。

核心遞歸邏輯

int dfs(int pos, int mark) {
    if (dp[pos][mark & 1] != -1) return dp[pos][mark & 1];
    if (G[pos].empty()) return dp[pos][mark & 1] = value[pos];
    
    int maxn = -1, minn = INF;
    for (int v : G[pos]) {
        if (mark & 1) maxn = max(maxn, dfs(v, mark + 1));
        else minn = min(minn, dfs(v, mark + 1));
    }
    int tmp = (mark & 1) ? maxn : minn;
    return dp[pos][mark & 1] = value[pos] + tmp;
}

完整代碼框架

const int N = 100055;
int dp[N][2], value[N], degree[N];
vector<int> G[N];
int n, m, f;

void init() { /* 初始化數組、向量 */ }
bool input() { /* 讀取 n,m,f、節點值、邊、入度 */ }

void cal() {
    int ans = -1;
    for (int i = 1; i <= n; i++)
        if (degree[i] == 0)
            ans = max(ans, dfs(i, 1));
    puts(ans < f ? "Glory" : "Victory");
}

int main() {
    while (true) {
        init();
        if (input()) return 0;
        cal();
    }
    return 0;
}