首页 > 代码库 > HDU 1074

HDU 1074

2024-07-29 15:35:13   217人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=1074

状压dp，记录路径

求最小值的状压dp非常裸，5分钟就写好了，记录路径有点麻烦，之前没怎么处理过这种问题

我的方法是用一个map建立当前状态和前驱状态的映射，输出要按字典序，因为已经按字典序从大到小排好了，所以状态值比较小的优先（字典序小）

#include <iostream>#include <cstdio>#include <cstring>#include <map>using namespace std;const int INF = 0xfffffff;struct fuck{    int w, pre;}dp[1<<15];struct node{    char name[105];    int D, C;}p[16];int cal(int x){    int res = 0, cnt = 0;    while(x){        if(x & 1){            res += p[cnt].C;        }        cnt++;        x >>= 1;    }    return res;}int cnt(int x){    int res = 0;    while(x){        if(x & 1){            res++;        }        x >>= 1;    }    return res;}int cal1(int x, int y){    int res = 0;    while(1){        if((x&1) != (y&1)){            return res;         }        res++;         x >>= 1; y >>= 1;     }}int ans[25], ct;    int main(){    int T;    scanf("%d", &T);    while(T--){        int n;        scanf("%d", &n);        for(int i = 0; i < (1<<n); i++)            dp[i].w = INF;        int xx = 0;        while(1){            dp[(1<<xx)].pre = 0;             xx++;             if(xx == n) break;        }        for(int i = 0;i < n; i++){            scanf("%s %d %d", p[i].name, &p[i].D, &p[i].C);            if(p[i].C > p[i].D)                dp[1<<i].w = p[i].C - p[i].D;            else                 dp[1<<i].w = 0;        }        map <int, int> mp;         for(int i = 0; i < (1<<n); i++){            for(int j = 0; j < n; j++){                if(i&(1<<j)){                    if(cal(i) > p[j].D){                        if(dp[i].w > dp[i^(1<<j)].w + cal(i) - p[j].D){                            dp[i].w = dp[i^(1<<j)].w + cal(i) - p[j].D;                            dp[i].pre = i^(1<<j);                             mp[i] = i^(1<<j);                            }                        else if(dp[i].w == dp[i^(1<<j)].w + cal(i) - p[j].D && dp[i].pre > (i^(1<<j))){                            dp[i].pre = i^(1<<j);                             mp[i] = i^(1<<j);                              }                            //dp[i] = min(dp[i], dp[i^(1<<j)] + cal(i) - p[j].D);                    }                    else{                        if(dp[i].w > dp[i^(1<<j)].w){                            dp[i].w = dp[i^(1<<j)].w;                            dp[i].pre = i^(1<<j);                            mp[i] = i^(1<<j);                         }                        else if(dp[i].w == dp[i^(1<<j)].w && dp[i].pre > (i^(1<<j))){                            dp[i].pre = i^(1<<j);                            mp[i] = i^(1<<j);                         }                        //dp[i] = min(dp[i], dp[i^(1<<j)]);                    }                }            }        }        printf("%d\n", dp[(1<<n)-1]);        int now = (1<<n) - 1;         ct = 0;         while(now){            ans[ct++] = cal1(now, mp[now]);            now = mp[now];         }        for(int i = n - 1; i >= 0; i--){            printf("%s\n", p[ans[i]].name);        }    }    return 0;}
View Code

 

HDU 1074


联系
我们