HDu 1074状圧dp

テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1074 标题:n個のジョブがあり、各ジョブに対してdeadlineがあり、このジョブを完了するのに要する時間がある.もしdeadlineを超えて1日に1点を差し引くならば、どのように宿題の順序を書いてやっと差し引く点数が最も少ないことを保証することができることを求めます.考え方:各ジョブには3つの要素、名前、ddlがあり、必要な時間があります.現在のジョブが完了していることを異なる状態で表し、状態圧dpを用いて集合Sを完了したジョブの集合と定義し、uを現在の集合Sにおけるジョブ番号とする.各状態にも3つの要素があり、1つはこの状態に達するために必要な時間であり、1つは最小のスコアであり、転送の経路を記録する必要があるため、どこから転送されたかを記録する必要がある.
i jが異なる状態を表すと、i^jはi状態がj状態を除いたものを表す.i&jはi状態にjが含まれている状態を表す.遷移方程式:tmpはS−{u}という状態から遷移し,マルチスナップのスコアが必要であることを示す.dp[S].lowscore = min(dp[S].lowscore,dp[S-{u}].lowscore + tmp); (uはSに属する)減点が更新されると,記録経路と更新に要する時間が同時に必要となる.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
#define M 20
#define INF 0x3f3f3f3f
struct
{
    int time;
    int lowscore;
    int pre;
}dp[1<<M];
struct
{
    int cost;
    int ddl;
    char name[109];
}course[M];
int n;
int main()
{
    //freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i = 0;i < n;i++)
        {
            scanf("%s %d %d",course[i].name,&course[i].ddl,&course[i].cost);
        }
        for(int i = 0;i < 1<<n;i++)
        {
            dp[i].time = 0;
            dp[i].lowscore = INF;
            dp[i].pre = -1;
        }
        dp[0].lowscore = 0;
        for(int S = 0;S < 1<<n;S++)
        {
            for(int u = 0;u < n;u++)
            {
                if(S & (1<<u))
                {
                    int temp = dp[S^(1<<u)].time + course[u].cost - course[u].ddl;
                    if(temp < 0) temp = 0;
                    if(dp[S].lowscore >= dp[S^(1<<u)].lowscore + temp) //              pre      ，           
                    {
                        dp[S].pre = u;
                        dp[S].lowscore = dp[S^(1<<u)].lowscore + temp;
                        dp[S].time = dp[S^(1<<u)].time + course[u].cost;
                    }
                }
            }
        }
        printf("%d
",dp[(1<<n)-1].lowscore);
        stack<int> ss;
        for(int i = (1<<n)-1;;)
        {
            ss.push(dp[i].pre);
            i = i ^ (1<<dp[i].pre);
            if(i == 0) break;
        }
        while(!ss.empty())
        {
            int temp;
            temp = ss.top();
            ss.pop();
            printf("%s
",course[temp].name);
        }
    }
    return 0;
}