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);
    }

}