Doing Homework

有n个任务，每个任务有一个截止时间，超过截止时间一天，要扣一个分。
求如何安排任务，使得扣的分数最少。

Input
有多组测试数据。第一行一个整数表示测试数据的组数
第一行一个整数n(1<=n<=15)
接下来n行，每行一个字符串(长度不超过100)表示任务的名称和两个整数，分别表示任务的截止时间和完成任务需要的天数。 这n个任务是按照字符串的字典序从小到大给出。 

Output
每组测试数据，输出最少扣的分数的。 并输出一个完成任务的方案，如果有多个方案，输出字典序最小的一个。

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

状态压缩dp,遇到这种状态不能像背包容量一样分割的情况。可以使用二进制来表示状态，来进行状态的转移。
拿此题第一个实例举例，使用 111 表示三个任务都完成，011表示第一，二个任务完成。010 表示第二个任务完成。以此类推。
所以状态转移的情况为：
---------------------------------------------------111
-----------------------------011-----------------101---------------------110
-----------------------001------010-------100-------001---------100-------010
上面的状态可以由下面的状态得到，例如，011 可以由 001 状态加上010来得到，也可以由010加上001来得到。由此我们可以先求出最底一层简单的状态，再求出最上面的最终状态。下面将结合代码详细讲解利用这种思想解题。代码中以第一个例子来讲解

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

int T, N;

struct node
{
    char name[106];
    int limit,use;
};

typedef struct node Node;

Node A[20];

int dp[1<<16];	//到第 i 个状态时所扣的分最小值

int time[1<<16];  //到第 i 个状态所经过的时间

int Path[1<<16];	//到达第 i 个状态所走的前一步路经

void PP(int x)
{
    if(x <= 0)
        return;

    PP(x - (1 << Path[x]));

    cout << A[Path[x]].name << endl;
}

int main()
{
    freopen("G:\\data.txt", "r", stdin);

    cin >> T;

    while(T--)
    {
        cin >> N;

        memset(A, 0, sizeof(A));
        memset(dp, 0, sizeof(dp));
        memset(time, 0, sizeof(time));
        memset(Path, 0, sizeof(Path));

        for(int i = 0; i < N; i++)
        {
            cin >> A[i].name >> A[i].limit >> A[i].use;
        }

        int tol = 1 << N;

        for(int i = 1; i < tol; i++)  //从001 状态到 111  状态枚举 
        {
            dp[i] = INT_MAX;

            for(int j = 0; j < N ; j++)      //试探第 j 个任务
            {
                int tmp = 1 << j;			//转换成对应的二进制表示
												//如果两个状态可以转移，则其中一个有相同的位，例如 011 和 001 最后一位都为1，011 和100就无法转换。
                if(!(tmp & i))              //无法由tmp状态转移到i，舍弃
                    continue;
												// i - tmp 为转换的中间状态，例如，011 可以由 001 + 010 转换而来， 当tmp 为001 时, i - tmp = 011 - 001 = 010 正好为转换的中间状态。
                int cc = time[i-tmp] + A[j].use - A[j].limit;   //可以由tmp状态转移到i状态
																				//
                if(cc < 0)
                    cc = 0;

                if(dp[i] >= cc + dp[i-tmp])  //因为要求字典序最小的，而且任务是按照字典序增大的顺序给出的,所以要加等于号
                {
                    dp[i] = cc + dp[i-tmp];
                    time[i] = time[i-tmp] + A[j].use;
                    Path[i] = j;
                }
            }
        }

        cout << dp[tol-1] << endl;

        PP(tol-1);
    }

    return 0;
}

这题给我最大的启示就是当遇到不能像背包容量那样分解时，可以考虑使用这种二进制进行状态分解和转移。