本帖最后由 善良的禽兽 于 2015-9-26 12:51 编辑
#include "cstdio"
#include "cmath"
#include "fstream"
#include "cstring"
#include "algorithm"
#include "iostream"
#include "vector"
#include "queue"
#include "stack"
#include "set"
#include "map"
#define lson root<<1
#define rson root<<1|1
#define lowbit(i) i&(-i)
#define debug(x) cout<<#x<<"="<<x<<endl;
#define here cout<<endl<<"_______________here "<<endl;
#define INF 0x7f7f7f7f
#define LINF 0x7f7f7f7f7f7f7f7f
#define Prime 999983
#define N 12
using namespace std;
struct
{
int a, b, c, d, e, f;
int maxa, maxb, maxc, maxd, maxe, maxf;
}sk[N];
int dp[1<<N][7];
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
int T, n, maxx;
scanf("%d", &T);
while(T--)
{
maxx = 0;
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%d%d%d%d%d%d", &sk.a, &sk.b, &sk.c, &sk.d, &sk.e, &sk.f);
sk.maxa = max(max(sk.b, sk.c), max(sk.d, sk.e));
sk.maxb = max(max(sk.a, sk.c), max(sk.e, sk.f));
sk.maxc = max(max(sk.a, sk.b), max(sk.d, sk.f));
sk.maxd = max(max(sk.a, sk.c), max(sk.e, sk.f));
sk.maxe = max(max(sk.a, sk.b), max(sk.d, sk.f));
sk.maxf = max(max(sk.b, sk.c), max(sk.d, sk.e));
}
memset(dp, 0, sizeof(dp));
for(int i = 0; i < n; i++)
{
dp[1<<i][sk.a] = max(dp[1<<i][sk.a], sk.maxa);
dp[1<<i][sk.b] = max(dp[1<<i][sk.b], sk.maxb);
dp[1<<i][sk.c] = max(dp[1<<i][sk.c], sk.maxc);
dp[1<<i][sk.d] = max(dp[1<<i][sk.d], sk.maxd);
dp[1<<i][sk.e] = max(dp[1<<i][sk.e], sk.maxe);
dp[1<<i][sk.f] = max(dp[1<<i][sk.f], sk.maxf);
}
for(int state = 0; state < (1<<n); state++)
{
for(int i = 0; i < n; i++)
{
if(state & (1<<i))
{
for(int j = 1; j <= 6; j++)
{
if(sk.a == j && dp[state ^ (1<<i)][sk.f])
dp[state][j] = max(dp[state][j], dp[state ^ (1<<i)][sk.f] + sk.maxa);
if(sk.b == j && dp[state ^ (1<<i)][sk.d])
dp[state][j] = max(dp[state][j], dp[state ^ (1<<i)][sk.d] + sk.maxb);
if(sk.c == j && dp[state ^ (1<<i)][sk.e])
dp[state][j] = max(dp[state][j], dp[state ^ (1<<i)][sk.e] + sk.maxc);
if(sk.d == j && dp[state ^ (1<<i)][sk.b])
dp[state][j] = max(dp[state][j], dp[state ^ (1<<i)][sk.b] + sk.maxd);
if(sk.e == j && dp[state ^ (1<<i)][sk.c])
dp[state][j] = max(dp[state][j], dp[state ^ (1<<i)][sk.c] + sk.maxe);
if(sk.f == j && dp[state ^ (1<<i)][sk.a])
dp[state][j] = max(dp[state][j], dp[state ^ (1<<i)][sk.a] + sk.maxf);
}
}
}
}
for(int i = 1; i <= 6; i++)
maxx = max(maxx, dp[(1<<n) - 1]);
printf("%d\n", maxx);
}
return 0;
}
|
|
收藏
淘帖
踩
