UVA690题：流水线调度（位运算+DFS剪枝）

今天这道题目可是花了不少时间才做出来的，一是一开始我完全没看懂题目，一脸懵逼完全；二是经历了无数次的超时，最后发现了原因——有一个剪枝的地方不小心写错了，多循环了好多次，但是答案还是正确的。。。这就非常尴尬了。

题目

首先给出传送门：https://vjudge.net/problem/UVA-690

首先这道题目的题意特别不好看懂，但是说破了就很简单，我一开始都差点要跳过这题了。我们有一台电脑，有10个程序需要电脑完成，我们的电脑有5个CPU，然后题目会给出一张表，这张表会把时间分成n个小块，然后每一个程序正好需要n个时间才可以完成（注意是1个程序，而我们总共有10个），然后关键的限制来了，一些特定的时间片上必须使用特定的CPU来工作。

估计看到这你还是迷糊的，我一开始也觉得很奇怪，那么我们来用下图的例子来说明一下：

首先我们有十个程序要跑对吧，但是我们不至于傻乎乎的一个接一个等着前一个程序全部跑完再跑下一个（这就是本题的意思了），比如，我们在时间0的时候开启程序a，然后等程序a执行到时间1的时候我们同时打开程序b，然后这就是两个程序交叠了一些时间（当然，b也得跑完一整个时间，所以时间0是程序b最后跑的时间片），但是题目中有限制，比如，a和b都往后继续跑，a跑到了时间5了，相对应的，b跑到了时间4，然后根据表中的X的位置，我们可以得知程序a需要调用第一个CPU，但是与此同时，程序b也需要调用第一个CPU，然后就矛盾了，这可没有什么并发呀锁的机制，直接就果断排除这种情况了。所以你需要做的就是在没有这种冲突的情况下尽量使这10个程序以最快的速度跑完，题目要求输入最小花费的时间片。

这下你可能大概明白这题的意思了，那么我们分析一下，首先毫无疑问最长的时间一定是10个程序一个接一个跑了，所以我们很容易就可以得到时间的上限进行剪枝，不过这个剪枝太弱了，我们需要找到更快的，能排除更多的。

我们可以模仿IDA*算法中我们剪枝的方法，假设我们已经找到了一个看起来还算不错的答案，我们可以用这个还不错的答案来对后面的答案进行剪枝。那么具体如何实现呢，我们得先讲讲位运算了。

我们可以使用位运算把每一个CPU需要的位置变成一个二进制的数字，只需要将“.”变成0，将“X”变成1即可。然后我们可以充分利用位运算的右移运算符对整个数字进行右移1位，2位等等，这样我们就可以方便的模拟出程序的相互交错了，然后我们再去逐个排查，如果发现有1的重合（就是同时要使用这一个CPU了），马上就排除整个移动位数，这样，我们就可以知道在哪个位置开新程序是可能的，在哪些程序位置开是绝对不行的。

然后我们就可以回到剪枝了，我们已经知道最小的合法的两个程序之间的间隔，那么我们就假设我们每一次都使用最小的间隔开程序（放缩法嘛，往最优的方向走），然后如果最优的方案都无法超过前面的答案，我们就之间return，因为这个情况已经没救了，这就是我们杀伤力最大的剪枝方法。

代码

#include <iostream>
using namespace std;
const int maxn=20;
const int N=5;
const int tot=10;
int state[N],ans;
int chart[maxn],num;

void dfs(int d,int* now,int sum){
    if(sum+ chart[0] * (tot-d)>=ans)
        return;
    for(int i=0;i<num;i++){
        int mov=chart[i];
        int flag=1;
        for(int j=0;j<N;j++){
            if((now[j]>>mov)&state[j]){
                flag=0;
                break;
            }
        }
        if(flag){
            if(d==9){
                ans=min(ans,sum+mov);
                return;
            }
            int next[N];
            for(int j=0;j<N;j++)
                next[j]=(now[j]>>mov)|state[j];
            dfs(d+1,next,sum+mov);
        }
    }
}

void init(int n){
    num=0;
    for(int mov=1;mov<=n;mov++){
        int flag=1;
        for(int i=0;i<N;i++){
            if((state[i]>>mov)&state[i]){
                flag=0;
                break;
            }
        }
        if(flag)
            chart[num++]=mov;
    }
}

int main(){
    //freopen("/home/eric/桌面/ACM/UVA/input.txt","r",stdin);
    int n;string in;
    while(cin>>n&&n){
        for(int i=0;i<N;i++){
            state[i]=0;
            cin>>in;
            for(int j=0;j<n;j++)
                if(in[j]=='X')
                    state[i]|=(1<<j);
        }
        ans=n*10;
        init(n);
        dfs(1,state,n);
        cout << ans << endl;
    }
    return 0;
}

ok,终于说完了这麻烦的一题，明天估计是最后两道搜索题了，后天开始二分和分治。
还有我们区块链的笔记每天应该都会更新，除非我偷懒了哈哈。