Most Powerful

題意：

n個(gè)原子，當(dāng)其中兩個(gè)原子碰撞時(shí)，其中一個(gè)會(huì)消失，產(chǎn)生大量能量。現(xiàn)在知道每?jī)蓚€(gè)原子的碰撞表現(xiàn)，求出產(chǎn)生的能量總和的最大值

題解:

設(shè)dp[i]表示i狀態(tài)下所獲得的能量
i為二進(jìn)制，第x位為1說明該位的原子已經(jīng)消失
當(dāng)j和k原子都還未消失（即i的第j位和第k位都是0），j和k碰撞會(huì)產(chǎn)生a[j][k]的能量，且k會(huì)消失，i將變成dp[i|(1<<k)]
所以得狀態(tài)轉(zhuǎn)移方程：

dp[i|(1<<k)] = max(dp[i|(1<<k)], dp[i] + a[j][k]);

因?yàn)樽詈罂隙〞?huì)剩下一個(gè)原子，所以枚舉每個(gè)原子被剩下的情況，取最大值

代碼：

#include <bits/stdc++.h>using namespace std;const int N = 20 + 5; typedef long long LL; int n, a[N][N], dp[1<<12]; int main() {while (scanf("%d", &n) && n != 0) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {cin >> a[i][j];}}memset(dp, 0, sizeof dp);int num = (1 << n) - 1;for (int i = 0; i <= num; i++) {for (int j = 0; j < n; j++) {if (!(i & (1 << j))) {for (int k = 0; k < n; k++) {if (!(i & (1 << k))) {dp[i|(1<<k)] = max(dp[i|(1<<k)], dp[i] + a[j][k]);}}}}}int res = 0;for (int i = 0; i < n; i++) {res = max(res, dp[num - (1 << i)]);}cout << res << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Most Powerful的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。