ZOJ 4257

ZOJ 4257
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

【題目大意】不超過10種氣體,兩兩之間相互碰撞可以產生一定的能量,如a碰b,那麼b氣體就消失,自身不能碰自身,問最後所能得到的最大能量。

【題目解析】用10位二進位制表示氣體是否存在,0表示存在,1表示不存在,S(上一個狀態)中的兩種氣體碰撞並且有一種消失,可以得到newS的狀態(狀態轉移)

【狀態表示】dp[state] 狀態為state時的最大能量

【轉移方程】dp[state] = max(dp[state],dp[state’] a[i][j])

【邊界條件】dp[i] = 0;

 注意dp時狀態由小到大,1表示被使用了,最大值一定是最後只剩一個的時候,優化20ms

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define LL long long
int const MAX = 1e6   1;
int const INF = 1 << 30;
double const EPS = 0.00000001;
using namespace std;
//dp[state]表示當前state產生的最大能量,1表示已結被使用了
int mp[10][10], n, dp[1 << 10];
int main(){
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
while (scanf("%d", &n) == 1 && n){
for (int i = 0; i < n; i  )
for (int j = 0; j < n; j  )
scanf("%d", &mp[i][j]);
//全部存在時為0
memset(dp, 0, sizeof(dp));
//不能從大到小,因為更新的是按照被使用的氣體數目遞增來更新的
// for (int s = (1 << n) - 1; s >= 1; s--){
//     for (int i = 0; i < n; i  ){
//         if (s & (1 << i) == 0) continue;
//         for (int j = 0; j < n; j  ){
//             if (j == i || (s & (1 << j) == 0)) continue;
//             int ns = s - (1 << j);
//             dp[ns] = max(dp[ns], dp[s]   mp[i][j]);
//         }
//     }
// }
for (int s = 0; s < (1 << n); s  ){
for (int i = 0; i < n; i  ){
if ((s & (1 << i))) continue;
for (int j = 0; j < n; j  ){
if (s & (1 << j) || i == j) continue;
int ns = s   (1 << j);
dp[ns] = max(dp[ns], dp[s]   mp[i][j]);
}
}
}
int maxv = (1 << n) - 1, ans = 0;
for (int i = 0; i < n; i  )
ans = max(ans, dp[maxv - (1 << i)]);
// printf("%d ", dp[maxv - (1 << i)]);
printf("%d\n", ans);
}
return 0;
}

 

相關文章

程式語言 最新文章