首页 > 代码库 > hdu 1074 Doing Homework（状压DP）
hdu 1074 Doing Homework（状压DP）
题意：
有N（N<=15）个作业，每个作业有个名字、上交截止时间、完成它所耗的时间。
一个作业每超期一天扣一分。
问小余如何安排做作业的顺序，才能使扣的分最少。
输出最少扣分，安排的顺序。
思路：
总共有N！个安排方案。暴力超时。所以想到用DP。
如何表示状态？N小于等于15，可以用状态压缩。
具体，，，，看代码吧，，
这里用前一个状态推导后一个状态的方式，这样好写。
代码：
struct node{ char name[105]; int deadline, days;}work[20];int n;int cn=0;int ds[36005];int dp[36005];int path[36005];void dfsCalc(int lastPos,int totalNum,int Num){ //正要打算从n个中选totalNum个，当前状态为Num if(totalNum<=0){ ds[++cn]=Num; return; } rep(i,lastPos+1,n-totalNum+1){ int NUM=Num+(1<<(i-1)); dfsCalc(i,totalNum-1,NUM); }}int calcState(int state){ int ans=0; rep(i,0,n-1){ int t=(state&(1<<i)); if(t!=0){ ans+=(work[i+1].days); } } return ans;}bool cmp(node a,node b){ return strcmp(a.name,b.name)<0;}int main(){ int T; cin>>T; while(T--){ scanf("%d",&n); rep(i,1,n){ scanf("%s%d%d",work[i].name,&work[i].deadline,&work[i].days); } sort(work+1,work+1+n,cmp); mem(dp,inf); rep(i,1,n){ int state=(1<<(i-1)); if(work[i].days>work[i].deadline){ dp[state]=work[i].days-work[i].deadline; path[state]=i; }else{ dp[state]=0; path[state]=i; } } rep(i,1,n-1){ cn=0; dfsCalc(0,i,0); rep(j,1,cn){ int oldState=ds[j]; rep(k,1,n){ if((oldState&(1<<(k-1)))==0){ int newState=oldState+(1<<(k-1)); int temp=calcState(oldState); if(temp+work[k].days>work[k].deadline){ if( dp[oldState]+temp+work[k].days-work[k].deadline<dp[newState] ){ dp[newState]=dp[oldState]+temp+work[k].days-work[k].deadline; path[newState]=k; } }else{ if( dp[oldState]<dp[newState] ){ dp[newState]=dp[oldState]; path[newState]=k; } } } } } } int N=(1<<n)-1; printf("%d\n",dp[N]); int ansPath[15]; int ansNum=0; while(N){ ansPath[++ansNum]=path[N]; N-=(1<<(path[N]-1)); } rep2(i,ansNum,1){ puts(work[ansPath[i]].name); } } return 0;}
hdu 1074 Doing Homework（状压DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。