本文共 960 字,大约阅读时间需要 3 分钟。
题意:任意两个能量球相撞,得到一个能量,此能量消失,问你最后能得到的最大能量题解:利用二进制压缩逆推,由11111状态推到00001等状态。
#include#include #include #include using namespace std;const int M = (1<<11)+3;int dp[M],a[M];int map[15][15];int main(){ int T,n; while(cin >> n,n){ for(int i = 0;i < n;i ++){ for(int j = 0;j < n;j++){ cin >> map[i][j]; } } int cnt = 1 << n; for(int i = cnt-1;i>=0;i-- ){ dp[i] = 0; for(int j = 0;j < n;j ++){ int ret = 1 << j; if(!(i&ret)) continue ; for(int k = 0;k < n;k++){ int res = 1 << k; if(res&i) continue; if(k == j) continue; dp[i] = max(dp[i],dp[i|res] + map[j][k]); } } } int ans = -1; for(int i = 0;i < cnt;i++) ans = max(ans,dp[i]);//寻找状态只剩一个气体的最大值 cout << ans <
转载地址:http://ddsgi.baihongyu.com/