701
hdu 1074 Doing Homework 狀態DP+dfs
從沒寫過狀態dp，隻是據說這是而已……
其實就是記錄個當前點下可以達到的最大值，隻有最大值更新後才向下級更新，過程就和spfa求最短路一樣……
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define INF 1E9
using namespace std;
struct node
{
char s[101];
int C,D,E;
};
node a[16];
int Min[70000];
int last[70000];
int ok;
int n,t;
void dfs(int time,int now,int ans)
{
if(now>=n)return;
for(int i=0;i<n;i++)
{
int m=1<<i;
if(ok&m)continue;
ok|=m;
t=time+a[i].E;
if(t<0)t=0;
if(ans+t<Min[ok])//記憶最大狀態
{
Min[ok]=ans+t;
last[ok]=ok&(~m);
dfs(time+a[i].C,now+1,ans+t);//繼續搜索
}
ok&=~m;
}
return;
}
void out(int t)//反向打印
{
if(t==0)return;
int tt=last[t],i;
out(tt);
t^=tt;
for(i=0;i<n;i++)
{
if(t&1)break;
t>>=1;
}
puts(a[i].s);
}
int main()
{
int T,i;
scanf("%d",&T);
while(T--)
{
ok=0;
memset(Min,127,sizeof(Min));
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s%d%d",a[i].s,&a[i].D,&a[i].C);
a[i].E=a[i].C-a[i].D;
}
dfs(0,0,0);
t=(1<<n)-1;
printf("%d\n",Min[t]);
out(t);
}
}
最後更新：2017-04-03 18:51:44