首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> 關於C++

ZOJ 3471 Most Powerful:狀態壓縮 DP 解決原子碰撞最大能量問題

     編輯:關於C++

問題建模

N ≤ 10 個原子,兩兩碰撞產生能量並消失一個。給定 gain[i][j] 表示 i 與 j 碰撞、j 消失產生的能量。求剩下一個原子時的最大總能量。

狀態定義

用 N 位二進制數 mask 表示當前存活原子集合(1=存在,0=已消失)。初始狀態 (1<,目標狀態為任意單一位為 1 的狀態。

狀態轉移

從狀態 mask 選兩個存活原子 i, j(i≠j),令 j 消失,轉移到 mask ^ (1<,獲得能量 gain[i][j]。
DP 方程:
dp[mask ^ (1<

遞推順序

按狀態中 1 的個數 **從大到小** 遞推(或直接枚舉所有 mask 從大到小),確保轉移來源已計算。

代碼實現


int dp[1<<10];
memset(dp, -0x3f, sizeof dp);
dp[(1< 0; --mask) {
    if (dp[mask] < 0) continue;
    for (int i = 0; i < n; ++i) if (mask & (1<

複雜度分析

狀態數 2^N ≤ 1024,每狀態枚舉 O(N^2) 對,總 O(N^2 2^N) ≈ 10^5,極快。
測試用例 ≤ 500,其中 N=10 的 ≤ 50 組,總運算量 < 5e6,輕鬆通過。

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved