Doing Homework HDU

Homework HDU"/>

Doing Homework HDU

题意就是有个人要完成作业，作业有完成期限，晚做一天扣一分。
然后那个人问你做作业的次序。
注意：扣分相同时，应该输出字典序最小的方案


做法：状压DP


dp[i][j]的i表示作业完成情况，是一个二进制数，如果第i位是1表示该作业已做，
是0表示未做；j表示最后一个完成的作业，dp[i][j]表示扣的分


预处理出某个完成情况需要花费的时间a[1<<16]


如何转移？很简单，枚举新做的作业编号，判断它没做过，枚举做这个需要扣几分（或者不扣），
便可以转移了


先把dp数组搞定，之后还有


由于字典序的原因，后面不能随意输出，我们枚举每个完成了的i，
寻找答案是ans的，并且字典序最小（往后推），保存在ret里


dfs倒推来搞定


dfs（i,j,dep） 表示当前序列为i，刚做作业j,是第n-dep个做，为了方便递归
b数组存当前情况,与ret数组比较

代码如下

#include<bits/stdc++.h>
using namespace std ;
const int INF=1e9 ;//MAX
int b[16],ret[16] ;
int n;
int dp[1<<17][16] ;//dp[i][j]表示作业完成情况为i时最后一个完成的作业是j时要扣的分
char s[17][100] ;//名称即Computer,English,Math... 
int last[17],need[17],a[1<<17] ;//last[i]表示最后期限,need[i]表示需要多少天完成,a[i]表示完成情况为i时所需要花费的时间  
void dfs(int i,int j, int dep) { //向后寻找，凑成完成的次序的字符串，然后选择最小的 b[dep]=j;if (i==(1<<j)) {int flag= 0;for (int ii=0; ii<n; ii++) {if (strcmp(s[b[ii]],s[ret[ii]]) <0) {flag=1 ;//有一个b[ii]表示的字符串比ret的小 break ;}}if (flag) {memcpy(ret,b,sizeof(b)) ;//把b赋给ret }return ;}for (int k=0; k<n; k++) { //上一个完成的作业是k if ((i&(1<<k))!=0 && k!=j) { //满足两个条件：1.我们这个作业在dep时已经完成 2.他不是我刚刚做的那个 int cost=0 ;if (a[i]>last[j]) cost=a[i]-last[j] ;//被扣的分数(因为是倒着推,后面的+need[i]就要变成-need[i],化简变成a[i])if (dp[i-(1<<j)][k]+cost==dp[i][j]) { //是最优答案的祖先（这个词语用的不太合适） dfs(i-(1<<j),k,dep-1) ;//向下继续搜 }}}
}
int main() {int T ;scanf("%d",&T) ;for(int e=1; e<=T; e++) {memset(a,0,sizeof(a)) ;//清空 scanf("%d",&n) ; //读入 for (int i=0; i<=n-1; i++) {scanf("%s%d%d",s[i],&last[i],&need[i]) ;}for (int i=0; i<=(1<<(n))-1; i++) { //计算完成情况为i时所花费的时间 for (int j=0; j<=n-1; j++)if ((i&(1<<j))!=0) a[i]+=need[j] ;}for (int i=0;i<=(1<<(n))-1; i++) //先全部初始为MAX for (int j=0;j<=n-1;j++)dp[i][j]=INF ;for (int i=0; i<=n-1;i++) { //只做一个作业的情况先预处理好 int t ;if (need[i]<=last[i]) t=0 ; //还没到限制时间,不扣分 else t=need[i]-last[i] ;//超过，扣分 dp[1<<i][i]=t;//赋值 }for (int i=0;i<(1<<(n));i++)  //枚举作业完成的情况for (int j=0; j<=n-1; j++) { //倒数第2个完成的作业if ((i&(1<<j))!=0){ //当前这个作业已做过，才能说可能是以前的状态 for (int k=0; k<=n-1; k++) { //新做的作业序号if ((i&(1<<k))==0) { //第k个作业还没有做过int cost=0 ;//扣分 if (a[i]+need[k]>last[k]) //是否已超出期限 cost=a[i]+need[k]-last[k] ;//扣分 if (dp[i|(1<<k)][k]>dp[i][j]+cost) //可以更新 dp[i|(1<<k)][k]=dp[i][j]+cost ;}}}}int ans=INF ;//最小答案 int i=(1<<(n))-1;for (int j=0; j<=n-1; j++) //搞出ans if (ans>dp[i][j]) ans=dp[i][j] ;printf("%d\n",ans) ;//答案先输出 char tmp[100]="A";//寻找s[i]中最大的字符串，给ret赋 MAX值 int maxs ;for (int i=0;i<n;i++)if (strcmp(s[i],tmp)>0) {strcpy(tmp,s[i]) ;maxs=i ;}for(int i=0;i<n;i++) ret[i]=maxs ; //赋 MAX for (int i=0;i<n;i++) {if(dp[(1<<n)-1][i]==ans) { //当前序列 dfs((1<<n)-1,i,n-1) ; //dfs }}for (int i=0;i<n;i++)printf("%s\n",s[ret[i]]) ;}return 0 ;
}