HDU - 1074 Doing Homework （狀壓DP）

                                         Doing Homework

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 14670    Accepted Submission(s): 7100

Problem Description

Ignatius has just come back school from the 30th ACM/ICPC. Now he has a lot of homework to do. Every teacher gives him a deadline of handing in the homework. If Ignatius hands in the homework after the deadline, the teacher will reduce his score of the final test, 1 day for 1 point. And as you know, doing homework always takes a long time. So Ignatius wants you to help him to arrange the order of doing homework to minimize the reduced score.

Input

The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.

Each test case start with a positive integer N(1<=N<=15) which indicate the number of homework. Then N lines follow. Each line contains a string S(the subject's name, each string will at most has 100 characters) and two integers D(the deadline of the subject), C(how many days will it take Ignatius to finish this subject's homework). 

Note: All the subject names are given in the alphabet increasing order. So you may process the problem much easier.

Output

For each test case, you should output the smallest total reduced score, then give out the order of the subjects, one subject in a line. If there are more than one orders, you should output the alphabet smallest one.

Sample Input

2

3

Computer 3 3

English 20 1

Math 3 2

3

Computer 3 3

English 6 3

Math 6 3

Sample Output

2

Computer

Math

English

3

Computer

English

Math

題意：求以某種順序完成作業時，扣分最少，且作業名稱的字典序最小。

思路：由于 (1<=N<=15) 的範圍很小，狀壓DP很合适，是以考慮用dp[ i ] （0 <= i < ( 1 << N ) ） 代表每個狀态的扣分的最小值，對于每個狀态 i ， 我們可以枚舉其每個已完成的作業 j ，然後求出以每個作業 j 為最後一門完成時的最小值即可。 對于輸出完成作業的順序，具體請看代碼。

//#include <bits/stdc++.h>
#include <map>
//#include <tr1/unordered_map>
#include<limits>
#include <float.h>
#include <list>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
inline int lowbit(int x){ return x & (-x); }
inline int read(){int X = 0, w = 0; char ch = 0;while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
    while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();return w ? -X : X;}
inline int gcd(int a, int b){ return b ? gcd(b, a % b) : a; }
inline int lcm(int a, int b){ return a / gcd(a, b) * b; }
#define For(i, x, y) for(int i=x;i<=y;i++)
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x)
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x)
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define db double
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int maxn = 1e6 + 10;
const int maxp = 1e3 + 10;
const LL INF = 0x3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int mod = 20090717;

const int MAXN = (1<<15) + 10;
int n;
char cname[20][150]; //課程名稱
int deadline[20], cost[20], dp[MAXN], finish[MAXN], pre[MAXN];
//對應的分别是：課程截止時間、課程時間花費、各狀态扣分最小值、各狀态完成時間、各狀态最優時以何門作業最後完成

void output(int x){
    if (!x) return;
    output(x-(1<<(pre[x]-1)));
    printf("%s\n", cname[pre[x]]);
}

int main()
{
    int t = read();
    while (t--){
        n = read();
        int ma = (1<<n)-1;
        For (i, 1, n) scanf("%s%d%d", cname[i], &deadline[i], &cost[i]);
        For (i, 1, ma){
            dp[i] = inf; //初始化到達轉态 i 的扣分
            _For (j, n, 1){ // j ( n -> 1 ) 逆序枚舉，是為了讓字典序較大的作業最後完成，就滿足了字典序較小的要求，
                            //且後面的判斷為 dp[i] > dp[i-temp] + add ，保證了即使有個 j' (j' < j),擁有和以
                            //第 j 門作業最後完成時的最小值，也不會是最優解，保證了字典序較大的作業最後完成。
                int temp = (1<<(j-1)); //第 j 門在轉态 i 的對應位置
                if (!(i&temp)) continue; //若轉态 i 中沒有完成作業 j，則跳過
                int add = finish[i-temp] + cost[j] - deadline[j]; //以第 j 門作業最後完成時的将要扣的分
                if (add < 0) add = 0; //在截止時間内完成，不需要扣分
                if (dp[i] > dp[i-temp] + add){
                    dp[i] = dp[i-temp] + add;
                    finish[i] = finish[i-temp] + cost[j];
                    pre[i] = j; //記錄轉态 i 扣分最少時，是以何門作業最後完成
                }
            }
        }
        printf("%d\n", dp[ma]);
        output(ma);
    }

    return 0;
}