ZOJ - 3471 Most Powerful (狀態壓縮)

ZOJ - 3471 Most Powerful (狀態壓縮)

題目大意：有n種原子，兩種原子相碰撞的話就會產生能量，其中的一種原子會消失。問這n種原子能產生的能量最大是多少

解題思路：用0表示該原子還沒消失，1表示該原子已經消失，那麼就可以得到狀態轉移方程了
dp[state | (1 << i)] = max(dp[state | (1 << i)], dp[state] + power[j][i])
上面的方程表示的是在state的情況下，用j原子去碰撞i原子，i原子消失所能得到的最大能量

注意這題：產生的能量有可能是負的

#include
#include
#include
using namespace std;
#define N 15
#define maxn 1200
int power[N][N];
int dp[maxn];
int n;

int main() {
    while(scanf(%d, &n) != EOF && n) {
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                scanf(%d, &power[i][j]);
        memset(dp, 0, sizeof(dp));

        for(int i = 0; i < (1 << n); i++)
            for(int j = 0; j < n; j++) {
                if((i & (1 << j)))
                    continue;
                for(int k = 0; k < n; k++) {
                    if(!(i & (1 << k)) && k != j) {
                        dp[i | (1 << j)] = max(dp[i | (1 << j)], dp[i] + power[k][j]);
                    }
                }
            }
        int ans = 0;
        for(int i = 0; i < (1 << n); i++)
            ans = max(ans, dp[i]);
        printf(%d
, ans);
    }
    return 0;
}