首页 > 代码库 > HDU 4924 Football Manager(状压DP)

HDU 4924 Football Manager(状压DP)

2024-07-16 16:37:39   225人阅读

题目连接 ： http://acm.hdu.edu.cn/showproblem.php?pid=4924

题意 ： n(<=20)个人选出11个人作为首发组成a-b-c阵容，每个人都有自己擅长的位置，并且每个人和其他人会有单向的厌恶和喜欢关系，每个人对于自己擅长的位置都有两个值CA和PA，有喜欢或者厌恶关系的两个人在一起也会影响整个首发的CA总值，要求选出一套阵容使得CA最大，或者CA一样的情况下PA最大。

思路 ： 状压搞，dp[s]s的二进制表示20个人中选了那几个人，然后规定选进来的顺序就是那个人所担当的位置，这样就可以避免知道状态的情况下去算最优而外加的复杂度了。

 

PS ：不过这道题目时限似乎卡得很紧，注意用lowbit()优化+其它一些优化，另外注意一些输入信息，关系中a和b有可能重复等细节就可以AC了。

  1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4 #include <map>  5   6 using namespace std;  7 map<int,int> mp;  8 const int INF = 0x3f3f3f3f;  9 typedef pair<int,int> PII; 10 const int MAXN = 1<<20; 11 int lowbit(int x) {return x&-x;} 12  13 int num[MAXN] = {0}; 14 int has[MAXN] = {0}; 15 int vis[MAXN] = {0}; 16 int Has[MAXN] = {0}; 17 int ans[MAXN]; 18 int abl[55][10]; 19 PII val[55][10]; 20 PII dp[MAXN]; 21 int state[22]; 22 int G[22][22]; 23 int n; 24 int tot; 25 int E; 26 void BUG(int a[], int n) { 27     for (int i = 1; i <= n; i++) { 28         printf("%d%c", a[i], " \n"[i == n]); 29     } 30 } 31  32 void init() { 33     num[0] = 0; vis[0] = 1; 34     tot = 1; E = 0; 35     for (int i = 1; i < MAXN; i++) { 36         if (!vis[i-lowbit(i)] || num[i-lowbit(i)] == 11)continue; 37         num[i] = num[i-lowbit(i)] + 1; has[i] = tot; Has[tot] = i; vis[i] = 1; 38         if (num[i] == 11) { 39             ans[++ E] = tot; 40         } 41         tot ++; 42     } 43     for (int i = 0; i < 20; i++) { 44         vis[1<<i] = i + 1; 45     } 46     //printf("tot = %d\n", tot); 47     return ; 48 } 49  50 PII update(PII a, PII b) { 51     return a < b ? b : a; 52     /* 53     if (a.first > b.first || a.first == b.first && a.second > b.second) { 54         return a; 55     }else { 56         return b; 57     } 58     */ 59 } 60 int c1, c2, c3, c4; 61 void add(int e, char s[], int C, int P) { 62     if (e > n) while (true); 63     if (s[0] == ‘G‘) { 64         val[e][1] = make_pair(C, P); 65         abl[e][1] = 1; 66         ++ c1; 67     }else if (s[0] == ‘D‘) { 68         val[e][2] = make_pair(C, P); 69         abl[e][2] = 1; 70         ++ c2; 71     }else if (s[0] == ‘M‘) { 72         val[e][3] = make_pair(C, P); 73         abl[e][3] = 1; 74         ++ c3; 75     }else { 76         val[e][4] = make_pair(C, P); 77         abl[e][4] = 1; 78         ++ c4; 79     } 80 } 81 bool used[MAXN]; 82 void solve() { 83     memset(used, false, sizeof(used)); 84     PII ret = make_pair(-INF, -INF); 85     dp[0] = make_pair(0, 0); used[0] = 1; 86     for (int ti = 1; ti < tot; ti++) { 87         int cnt = num[Has[ti]]; 88         int i = Has[ti]; 89         dp[ti] = make_pair(-INF, -INF); 90         for (int j = i; j > 0; j -= lowbit(j)) { 91             int nex = vis[lowbit(j)]; 92             int ts = has[i-lowbit(j)]; 93             if (!used[ts]) continue; 94             if (!abl[nex][state[cnt]]) continue; 95             dp[ti] = update(dp[ti], make_pair(dp[ts].first+val[nex][state[cnt]].first, dp[ts].second+val[nex][state[cnt]].second)); 96             used[ti] = 1; 97         } 98         if (cnt == 11 && used[ti]) { 99             int tmp = 0;100             for (int j = i; j > 0; j -= lowbit(j)) {101                 int now = vis[lowbit(j)];102                 for (int k = j; k > 0; k -= lowbit(k)) {103                     int nex = vis[lowbit(k)];104                     if (now != nex)tmp += G[now][nex] + G[nex][now];105                     else tmp += G[now][nex];106                 }107             }108             ret = update(ret, make_pair(dp[ti].first+tmp, dp[ti].second));109         }110     }111     if (ret.first == -INF) {112         printf("Poor Manager!\n");113     }else {114         printf("%d %d\n", ret.first, ret.second);115     }116     return ;117 }118 119 int main() {120     init();121     int T;122     scanf("%d", &T);123     for (int cas = 1; cas <= T; cas++) {124         scanf("%d", &n);125         memset(abl, 0, sizeof(abl));126         memset(G, 0, sizeof(G));127         c1 = 0, c2 = 0, c3 = 0, c4 = 0;128         mp.clear();129         for (int i = 1; i <= n; i++) {130             int e, m;131             scanf("%d%d", &e, &m);132             mp[e] = i;133             char ts[5];134             int tc, tp;135             for (int j = 1; j <= m; j++) {136                 scanf("%s %d%d", ts, &tc, &tp);137                 add(i, ts, tc, tp);138             }139         }140         int Q;141         scanf("%d", &Q);142         while (Q--) {143             int a, b, c;144             char ts[11];145             scanf("%d%d%s%d", &a, &b, ts, &c);146             a = mp[a]; b = mp[b];147             if (ts[0] == ‘L‘) {148                 G[a][b] = c;149             }else {150                 G[a][b] = -c;151             }152         }153         int nd, nm, ns;154         scanf("%d-%d-%d", &nd, &nm, &ns);155         if (n < 11 || c1 < 1 || c2 < nd || c3 < nm || c4 < ns) {156             printf("Poor Manager!\n"); continue;157         }158         state[1] = 1;159         for (int i = 2; i <= nd+1; i++) state[i] = 2;160         for (int i = 2+nd; i <= nd+1+nm; i++) state[i] = 3;161         for (int i = 2+nd+nm; i <= 11; i++) state[i] = 4;162         //for (int i = 1; i <= 11; i++) printf("%d%c", state[i], " \n"[i == 11]);163         //BUG(state, 11);164         solve();165     }166     return 0;167 }
View Code

 

//因为免费，所以在京东搭了一个网站，玩了几天，觉得还是暂时用cnblogs吧，等我icpc结束了再去搭站玩吧 *_*


联系
我们