黑马程序员技术交流社区

标题: DP [打印本页]

---

作者: 善良的禽兽    时间: 2015-9-26 12:44
标题: DP


#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;
}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2