HDU1074(상태 압축 dp4)

#include
#include
#include
#include
#include
#include
using namespace std;
struct
{
        string name;
        int cost,dead;
}object[30];
struct
{
        int time,score,pre,now;
}dp[1<<16];
int main()
{
        int t;
        scanf("%d",&t);
        while(t--)
        {
                int n;
                scanf("%d",&n);
                memset(dp,0,sizeof(dp));
                for(int i=0;icin>>object[i].name>>object[i].dead>>object[i].cost;
                int end=1<for(int i=1;i//  
                {
                        dp[i].score=1000000000;
                        for(int j=0;jint temp=1<if(temp&i)
                                {
                                        int past=i-temp;
                                        int grade=max(dp[past].time+object[j].cost-object[j].dead,0);
                                        if(dp[i].score>=grade+dp[past].score)//j 0       =，   n-1     =
                                        {
                                                dp[i].score=grade+dp[past].score;
                                                dp[i].time=dp[past].time+object[j].cost;
                                                dp[i].pre=past;
                                                dp[i].now=j;
                                        }
                                }
                        }

                }
                printf("%d
",dp[end-1].score);
                stack<int> s;
                int t=end-1;
                while(t)
                {
                        s.push(dp[t].now);
                        t=dp[t].pre;
                }
                while(!s.empty())
                {
                        cout<