黑马程序员技术交流社区

标题: 动态规划 [打印本页]

---

作者: 善良的禽兽    时间: 2015-9-26 12:48
标题: 动态规划

#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[i].a, &sk[i].b, &sk[i].c, &sk[i].d, &sk[i].e, &sk[i].f);
                                                                                         sk[i].maxa = max(max(sk[i].b, sk[i].c), max(sk[i].d, sk[i].e));
                                                                                         sk[i].maxb = max(max(sk[i].a, sk[i].c), max(sk[i].e, sk[i].f));
                                                                                         sk[i].maxc = max(max(sk[i].a, sk[i].b), max(sk[i].d, sk[i].f));
                                                                                         sk[i].maxd = max(max(sk[i].a, sk[i].c), max(sk[i].e, sk[i].f));
                                                                                         sk[i].maxe = max(max(sk[i].a, sk[i].b), max(sk[i].d, sk[i].f));
                                                                                         sk[i].maxf = max(max(sk[i].b, sk[i].c), max(sk[i].d, sk[i].e));
                                                 }
                                                                        memset(dp, 0, sizeof(dp));
                                                                        for(int i = 0; i < n; i++)
                                                                        {
                                                                                                                 dp[1<<i][sk[i].a] = max(dp[1<<i][sk[i].a], sk[i].maxa);
                                                                                                                 dp[1<<i][sk[i].b] = max(dp[1<<i][sk[i].b], sk[i].maxb);
                                                                                                                 dp[1<<i][sk[i].c] = max(dp[1<<i][sk[i].c], sk[i].maxc);
                                                                                                                 dp[1<<i][sk[i].d] = max(dp[1<<i][sk[i].d], sk[i].maxd);
                                                                                                                 dp[1<<i][sk[i].e] = max(dp[1<<i][sk[i].e], sk[i].maxe);
                                                                                                                 dp[1<<i][sk[i].f] = max(dp[1<<i][sk[i].f], sk[i].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[i].a == j && dp[state ^ (1<<i)][sk[i].f])
                                                                                                                                                                                                                                                                                        dp[state][j] = max(dp[state][j], dp[state ^ (1<<i)][sk[i].f] + sk[i].maxa);

                                                                                                                                                                                                                                                                 if(sk[i].b == j && dp[state ^ (1<<i)][sk[i].d])
                                                                                                                                                                                                                                                                                        dp[state][j] = max(dp[state][j], dp[state ^ (1<<i)][sk[i].d] + sk[i].maxb);

                                                                                                                                                                                                                                                                 if(sk[i].c == j && dp[state ^ (1<<i)][sk[i].e])
                                                                                                                                                                                                                                                                                        dp[state][j] = max(dp[state][j], dp[state ^ (1<<i)][sk[i].e] + sk[i].maxc);

                                                                                                                                                                                                                                                                 if(sk[i].d == j && dp[state ^ (1<<i)][sk[i].b])
                                                                                                                                                                                                                                                                                        dp[state][j] = max(dp[state][j], dp[state ^ (1<<i)][sk[i].b] + sk[i].maxd);

                                                                                                                                                                                                                                                                 if(sk[i].e == j && dp[state ^ (1<<i)][sk[i].c])
                                                                                                                                                                                                                                                                                        dp[state][j] = max(dp[state][j], dp[state ^ (1<<i)][sk[i].c] + sk[i].maxe);

                                                                                                                                                                                                                                                                 if(sk[i].f == j && dp[state ^ (1<<i)][sk[i].a])
                                                                                                                                                                                                                                                                                        dp[state][j] = max(dp[state][j], dp[state ^ (1<<i)][sk[i].a] + sk[i].maxf);
                                                                                                                                                                                                                }
                                                                                                                                                                 }
                                                                                                                 }
                                                                        }
                                                                        for(int i = 1; i <= 6; i++)
                                                                                                 maxx = max(maxx, dp[(1<<n) - 1][i]);
                                                                        printf("%d\n", maxx);
                }
                return 0;
}

---

作者: 阿秋    时间: 2015-9-26 19:03
http://bbs.itheima.com/home.php? ... dit&op=exchange

---

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

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