首页 > 代码库 > hdu 1074 Doing Homework
hdu 1074 Doing Homework
http://acm.hdu.edu.cn/showproblem.php?pid=1074
状压dp不是很懂,看着别人的代码写的,很长时间才看懂。 dp[i]记录(1<<n)-1个状态第i状态的最小结果。用pre数组记录每一个状态的前驱。
用dfs输出路径。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 16 5 using namespace std; 6 const int inf=1<<29; 7 8 int dp[1<<16]; 9 int t,n;10 int pre[1<<16];11 struct node12 {13 char name[110];14 int d;15 int c;16 }p[maxn*10];17 18 void dfs(int w)19 {20 if(w==0) return ;21 int pos=0;22 for(int i=0; i<n; i++)23 {24 if((w&(1<<i))!=0&&(pre[w]&(1<<i))==0)25 {26 pos=i;27 break;28 }29 }30 dfs(pre[w]);31 printf("%s\n",p[pos].name);32 }33 34 int main()35 {36 scanf("%d",&t);37 while(t--)38 {39 scanf("%d",&n);40 for(int i=0; i<n; i++)41 {42 scanf("%s%d%d",p[i].name,&p[i].d,&p[i].c);43 }44 for(int i=0; i<(1<<n); i++)45 {46 dp[i]=inf;47 }48 dp[0]=0;49 for(int i=0; i<(1<<n); i++)50 {51 for(int j=0; j<n; j++)52 {53 if(i&(1<<j)) continue;54 int sum=0;55 for(int k=0; k<n; k++)56 {57 if(i&(1<<k)) sum+=p[k].c;58 }59 sum+=p[j].c;60 if(sum>p[j].d) sum-=p[j].d;61 else sum=0;62 if(dp[i|(1<<j)]>dp[i]+sum)63 {64 dp[i|(1<<j)]=dp[i]+sum;65 pre[i|(1<<j)]=i;66 }67 }68 }69 printf("%d\n",dp[(1<<n)-1]);70 dfs((1<<n)-1);71 }72 return 0;73 }
hdu 1074 Doing Homework
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。