题目描述：

    原题地址：http://acm.hdu.edu.cn/showproblem.php?pid=3265

    很多很多海报，每张海报又被挖掉了一个长方形。求这些海报的覆盖面积。

题目分析：

    一张海报可以拆成四个矩形处理。线段树。

小结：

Long long 还是不要用printf输出，用cout吧……

题目描述：

    原题地址：http://acm.hdu.edu.cn/showproblem.php?pid=3237

    题目可以抽象成这样，有0~7这样8个数字组成的数字串，可以抽出k个数字再插回到任意位置，问最后不同的数字段（相同的数字组成一段，例如00077112有4段，000为一段，77为一段……）

题目分析：

    这个题乍一看很像动态规划，但是真的是动态规划，不过我还是第一次做这样的动态规划。

    参考了一位大牛的报告，地址如下：

F[i][j][k][s]，表示前i本书，拿走j本，留下的书最后一本高k（呃我觉得这个很巧妙），留下的书的组合为s（例如1010000表示高度为0的，高度为2的书有留下的）

    状态转移部分伪代码（当处理到f[i][j][k][s]时）

(1)  考虑第i本书不抽走，在f[i-1][j][k][s]存在的前提下（也就是处理到i-1本书的时候，这个状态下，留下的最后一本书高度为k）：

若这本书的高度也是k，那么这本书的加入不会造成混乱度的提升，则f[i][j][k][s] = min(f[i][j][k][s], f[i-1][j][k][s])

若这本书的高度不是k，那么这本书的加入会造成混乱度增加1，则f[i][j][k][s] = min(f[i][j][k][s], f[i-1][j][k][s] + 1)

（2）考虑抽走第i本书，f[now][j+1][k][s] = min( f[pre][j][k][s], f[now][j+1][k][s])

最后处理答案的时候要考虑一下那些被抽走的书还是要插回去的。如果有一本高度为h的书被抽走，剩下的书里头都没有高度为h的，那么混乱度需要增加。

代码：

hdu3237
#include <cstdio>
#include <cstdlib>

const int maxn = 101;
const int INF = 200;
const int total_s = 1<<8 + 1;

int f[2][maxn][9][total_s];
int n,take,all;
int h[maxn];

bool init(){
    int i,j,k,s;
    scanf("%d%d", &n, &take);
    if (n==0 && take==0) return false;
    all = 0;
    for (i=1; i<=n; i++){
        scanf("%d", &h[i]);
        h[i] -= 25;
        all |= (1<<h[i]);
    }
    
    return true;
}

int solve(){
    int i,j,k,s,temp,ans,now, pre;

    for (j=0; j<=take; j++)
        for (k=0; k<=8; k++)
            for (s=0; s<=1<<8; s++)
                f[0][j][k][s] = INF;
    f[0][0][8][0] = 0;

    for (i=1; i<=n; i++){
        
        now = i%2; pre = (i-1)%2;
        for (j=0; j<=take; j++)
            for (k=0; k<=8; k++)
                for (s=0; s<=1<<8; s++)
                    f[now][j][k][s] = INF;
                    
        for (j=0; j<=i && j<=take; j++)
            for (k=0; k<=8; k++)
                for (s=0; s<(1<<8); s++){
                    //save this one
                    if (f[pre][j][k][s]!=INF){
                        if (h[i] == k && f[pre][j][k][s] < f[now][j][k][s])
                            f[now][j][k][s] = f[pre][j][k][s];
                        if (h[i] != k && f[pre][j][k][s]+1 < f[now][j][h[i]][s|(1<<h[i])])
                            f[now][j][h[i]][s|(1<<h[i])] = f[pre][j][k][s]+1;
                    }
                    //get this one
                    if (j<take && f[pre][j][k][s]!= INF){
                        if (f[pre][j][k][s] < f[now][j+1][k][s])
                            f[now][j+1][k][s] = f[pre][j][k][s];
                    }
                }
    }
    ans = INF;
    int t = n%2;
    for (k=0; k<=8; k++)
        for (s=0; s<(1<<8); s++)
            if (f[t][take][k][s] != INF){
                temp = f[t][take][k][s];
                int temp_s = s;
                for (i=0; i<=7; i++)
                    if (((1<<i)&temp_s) == 0 && ((1<<i)&all) != 0){
                        ++temp;
                        temp_s = (1<<i) | s;
                    }
                if (temp<ans) ans = temp;
            }
    return ans;
}

int main(){
    int T(0);
    while (init()){
        int s = solve();
        printf("Case %d: %d\n\n", ++T, s);
    }
    return 0;
}
    

题目描述：

    原题地址：http://acm.hdu.edu.cn/showproblem.php?pid=3231

    给定一些正方体的关系，要求一组符合这些关系的正方体坐标，如果不存在符合条件的正方体坐标，IMPOSSIBLE。(Special Judge)

题目分析：

    首先把正方体这个立体问题拆分成X，Y，Z三个维度上的的平面问题。三个维度上的平面问题处理完了，正方体问题也就处理完了。

    首先想到了差分约束系统，但是我的SPFA呃，TLE了……（求一个不TLE的差分约束系统标程……）

    上网搜索了一个大牛的文，说只需要拓补排序就可以了，完全不需要差分约束。

    再想一想，此题如果用差分约束系统来做，所有边权都是-1。其实不如更直观地进行构图，例如a<b，那么就构图map[a][b] = 1，也就是不妨看做a到b的边权为1。其实进行一下拓补排序，根据点的拓补排序的结果就可以直接作为答案输出，如果拓补排序失败也就是IMPOSSIBLE。

代码：

hdu3231
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#define MAXN 2010
#define MAXR 500000
#define MAX 999999

typedef struct edges{
    int v,w,next;
}edge;

int N, R;
edge edge_X[MAXR], edge_Y[MAXR], edge_Z[MAXR];
int s_X[MAXN], s_Y[MAXN], s_Z[MAXN];
int index_X[MAXN], index_Y[MAXN], index_Z[MAXN];
int degree_X[MAXN], degree_Y[MAXN], degree_Z[MAXN];

void Add(struct edges e[], int start, int end, int index[], int degree[], int &tot){
    e[tot].v = end;
    e[tot].next = index[start];
    index[start] = tot++;
    degree[end]++;
}

bool init(){
    int i, totx, toty, totz; 
    scanf("%d%d", &N, &R);
    if (N == 0 && R == 0) return false;
    memset(index_X, 255, sizeof(*index_X)*MAXN); //-1 indicates end of link
    memset(index_Y, 255, sizeof(*index_Y)*MAXN); 
    memset(index_Z, 255, sizeof(*index_Z)*MAXN); 
    memset(degree_X, 0, sizeof(*degree_X)*MAXN);
    memset(degree_Y, 0, sizeof(*degree_Y)*MAXN);
    memset(degree_Z, 0, sizeof(*degree_Z)*MAXN);
    totx = toty = totz = 0;
    
    for (i=1; i<=N; i++){
        // node 0是超级汇点，最大的点。值为0
        Add(edge_X, 0, i, index_X, degree_X, totx);         //x1 of n-th Cube
        Add(edge_Y, 0, i, index_Y, degree_Y, toty);
        Add(edge_Z, 0, i, index_Z, degree_Z, totz);
        Add(edge_X, i, i+N, index_X, degree_X, totx);
        Add(edge_Y, i, i+N, index_Y, degree_Y, toty);
        Add(edge_Z, i, i+N, index_Z, degree_Z, totz);
    }
    for (i=1; i<=R; i++){
        char t[10];
        int  A, B;
        scanf("%s%d%d", t, &A, &B);
        if (t[0] == 'I'){
            Add(edge_X, A, B+N, index_X, degree_X, totx);        //x1(A) < x1(B)
            Add(edge_X, B, A+N, index_X, degree_X, totx);        //x2(A) > x1(B) or x1(B) < x2(A)
            Add(edge_Y, A, B+N, index_Y, degree_Y, toty);
            Add(edge_Y, B, A+N, index_Y, degree_Y, toty);
            Add(edge_Z, A, B+N, index_Z, degree_Z, totz);
            Add(edge_Z, B, A+N, index_Z, degree_Z, totz);
        }
        if (t[0] == 'X')
            Add(edge_X, A+N, B, index_X, degree_X, totx);    //x2(A) < x1(B)
        if (t[0] == 'Y')
            Add(edge_Y, A+N, B, index_Y, degree_Y, toty);    //y2(A) < y1(B)
        if (t[0] == 'Z')
            Add(edge_Z, A+N, B, index_Z, degree_Z, totz);    //z2(A) < z1(B)    
    }
    return true;
}

bool NonPreFirstTopSort(edge e[], int index[], int degree[], int n, int s[]){
    int i, count(0), head(0), tail(1);
    int Q[MAXN];
    
    Q[0] = 0;
    
    while (head != tail){
        s[Q[head]] = count++;
        i = index[Q[head]];
        while (i != -1){
            if (--degree[e[i].v] == 0) Q[tail++] = e[i].v;
            i = e[i].next;
        }
        ++head;
    }
    
    if (count < n) return false;
    else return true;
}

int main(){
    int Cases = 0, i;
    while (init() && ++Cases){
        bool flag;
        flag = NonPreFirstTopSort(edge_X, index_X, degree_X, N*2 + 1, s_X);
        if (flag) flag = NonPreFirstTopSort(edge_Y, index_Y, degree_Y, N*2 + 1, s_Y);
        if (flag) flag = NonPreFirstTopSort(edge_Z, index_Z, degree_Z, N*2 + 1, s_Z);
        if (flag){
            printf("Case %d: POSSIBLE\n", Cases);
            for (i=1; i<=N; i++)
                printf("%d %d %d %d %d %d\n", s_X[i], s_Y[i], s_Z[i], s_X[i+N],  s_Y[i+N], s_Z[i+N]);
            printf("\n");
            
        }
        else
            printf("Case %d: IMPOSSIBLE\n\n", Cases);
    }
    //system("pause");
    return 0;
}