首页 > 代码库 > HDU 1074-Doing Homework(状压DP)
HDU 1074-Doing Homework(状压DP)
题目链接:点击打开链接
做了好久。。一开始想爆搜就写啊写啊觉着15!的阶乘再怎么剪枝好像也是过不了的。。尤其是爆搜的时候字典序不好处理啊 后来问了飞神是状压DP。。sad当时根本不懂什么叫状压啊
题意:有n份家庭作业 给出每一份的期限和完成的该作业需要的时间,求安排完成作业的最优顺序,使得扣分最少(超过期限要扣分)
思路:把每份作业的完成情况看出2进制下的状态, 二进制从右到左一次对应作业 1 2.。。n ,对应位为1代表该位对应的作业已完成,反之亦然。所以总的状态有2^n-1种,
dp[2^n-1]代表所有的作业都完成了,dp[0]代表作业都还没完成。dp数组开成结构体类型的,dp[i] 保存当前减分的情况,前缀,以及当前的时间。从0递推 。递归打印。其中多数操作涉及到位运算,初看很没头脑,看一下位运算的定义就好了
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <string> #include <cctype> #include <vector> #include <cstdio> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #define maxn 1<<16 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 100000000 #define pp pair<int,int> #define ull unsigned long long using namespace std; struct node { int cost,re,pre; }dp[maxn]; char s[16][106];int n,c[16],d[16]; bool vis[maxn]; void init() { dp[0].cost=0; dp[0].pre=-1; dp[0].re=0; memset(vis,0,sizeof(vis)); } void output(int sb) { int cur=dp[sb].pre^sb,cnt=0; while(cur){cnt++;cur>>=1;} if(dp[sb].pre!=0)output(dp[sb].pre); printf("%s\n",s[cnt]); } void solve() { int tot=(1<<n)-1; for(int i=0;i<tot;i++) { for(int j=1;j<=n;j++) { int cur=1<<(j-1); if(!(cur&i)) { int tem=cur|i; dp[tem].cost=dp[i].cost+c[j]; int reduce=dp[tem].cost<d[j]?0:dp[tem].cost-d[j]; reduce+=dp[i].re; if(vis[tem]&&reduce<dp[tem].re) { dp[tem].re=reduce; dp[tem].pre=i; } if(!vis[tem]) { vis[tem]=1; dp[tem].re=reduce; dp[tem].pre=i; } } } } printf("%d\n",dp[tot].re); output(tot); } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%s %d %d",s[i],&d[i],&c[i]); init(); solve(); } return 0; }
HDU 1074-Doing Homework(状压DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。