Pipeline Scheduling（UVA 690）

网址如下：

Pipeline Scheduling - UVA 690 - Virtual Judge (vjudge.net)

（第三方网站）

噫，好！我中了！

这题还是有点折磨的，刚开始我只会递归下一个程序运行的时间（范围在1~n），很明显，直接TLE，然后用C++STL里面的bitset容器来表示所有的程序运行状况（因为最差情况下最长的时间段是200，用longlong只有64位，不够表示），结果vjudge上直接表示Compile Error，应该是不能用

最后是上CSDN上去看其他人的解题思路：

http://t.csdnimg.cn/AxOel

其中，把时间段200缩短到20的方法启发了我，而且里面提到的jump数组也减少的了递归量

妙哉

按这个思路自己写了一下之后是AC了

代码如下：

#include<cstdio>
#include<cstring>
typedef long long LL;const int maxn = 20;LL unit[5];
int jump[maxn], cnt;//jump的个数
int n, ans;void init(void){memset(unit, 0, sizeof(unit));ans = n * 10; getchar(); cnt = 0;
}
void getjump(void){LL unit_t[5]; memcpy(unit_t, unit, sizeof(unit));for(int i = 1; i <= n; i++){bool is = true;for(int j = 0; j < 5; j++){unit_t[j] <<= 1;if(unit[j] & unit_t[j]) is = false;}if(is) jump[cnt++] = i;}
}
void dfs(LL state[5], int sum, int m){//剪枝if(sum + jump[0] * (10 - m) > ans) return;//尝试部署for(int i = 0; i < 5; i++) if(unit[i] & state[i]) return;//部署for(int i = 0; i < 5; i++) state[i] |= unit[i];//下一个if(m == 10) ans = sum;elsefor(int i = 0; i < cnt; i++){int val = jump[i];LL * p = new LL [5];for(int j = 0; j < 5; j++) p[j] = state[j] >> val;dfs(p, sum + val, m + 1);delete [] p;}
}int main(void)
{while(scanf("%d", &n) == 1 && n){//初始化init();//输入for(int i = 0; i < 5; i++){int tmp = 1; char c;for(int j = 0; j < n; j++, tmp <<= 1)if((c = getchar()) == 'X') unit[i] |= tmp;getchar();}//得出答案getjump(); LL state[5]{};dfs(state, n, 1);printf("%d\n", ans);}return 0;
}