dfs 20 染色 代码公开
2025-04-28 13:04:36
发布于：广东
14阅读
0回复
0点赞
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int a[55];
int n;
int check(int state){
int lstr = -1, lstb = -1;
int ans = 0;
for(int i = 0; i <= n; i++){
if(state >> i & 1){
if(lstr != -1 && a[lstr] == a[i]) ans += a[i];
lstr = i;
}else{
if(lstb != -1 && a[lstb] == a[i]) ans += a[i];
lstb = i;
}
}
return ans;
}
void solve(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
int ans = 0;
for(int i = 0; i < (1ll << n); i++) ans = max(ans, check(i));
cout << ans << '\n';
for(int i = 1; i <= n; i++) a[i] = 0;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
有帮助，赞一个