UVA690-Pipeline Scheduling(dfs+二进制压缩状态)

发布时间：2020-12-14 05:06:08 所属栏目：百科来源：网络整理

导读：Problem?UVA690-Pipeline Scheduling Accept：142? Submit：1905 Time Limit: 3000 mSec ?Problem Description ? ? ? ?Input ? ? ?Output ? ? ?Sample Input 7 X...XX. .X..... ..X.... ...X... ......X 0 ? ?Sample Ouput 34 ? 题解：dfs的思路不难，剪枝也

Problem?UVA690-Pipeline Scheduling

Accept：142? Submit：1905

Time Limit: 3000 mSec

?Problem Description

?Input

?Output

?Sample Input

7
X...XX.
.X.....
..X....
...X...
......X
0

?Sample Ouput

题解：dfs的思路不难，剪枝也很容易想到，最优化剪枝。这个题主要是实现时的技巧性比较强。一开始没有想到只存阶段性的表，直接最大5*200，根本就不会往二进制的方向去想，看到别人题解的标题时二进制才意识到这一点，对于每一次搜索到的下一个可能的合理位置，当要继续递归下去时，这一次找到的合理位置和上一次的起始位置之间的表就已经没有意义了（对于这个方向继续向下的递归来说），直接位运算删掉即可，这样每时每刻都至多是5*20，开个int s[5]即可。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 
 6 using namespace std;
 7 
 8 const int N = 5,maxn = 25;
 9 
10 int n,cnt,Min;
11 int table[N],skip[maxn];
12 
13 bool Judge(int *num,int step){
14     for(int i = 0;i < N;i++){
15         if((num[i]>>step)&table[i]) return false;
16     }
17     return true;
18 }
19 
20 void init(){
21     memset(table,0,sizeof(table));
22     char str[maxn];
23     cnt = 0,Min = n*10;
24 
25     for(int i = 0;i < N;i++){
26         scanf("%s",str);
27         for(int j = 0;j < n;j++){
28             if(str[j] == ‘X‘) table[i] |= (1<<j);
29         }
30     }
31 
32     for(int i = 0;i <= n;i++){
33         if(Judge(table,i)) skip[cnt++] = i; 
34     }
35 }
36 
37 void dfs(int *s,int d,int time){
38     if(d == 10){
39         Min = min(Min,time);
40         return;
41     }
42 
43     if(time+skip[0]*(10-d) > Min) return;
44 
45     for(int i = 0;i < cnt;i++){
46         if(Judge(s,skip[i])){
47             int tmp[N];
48             for(int j = 0;j < N;j++){
49                 tmp[j] = ((s[j]>>skip[i]) | table[j]);
50             }
51             dfs(tmp,d+1,time+skip[i]);
52         }
53     }
54 }
55 
56 int main()
57 {
58 #ifdef GEH
59     freopen("input.txt","r",stdin);
60 #endif
61     while(~scanf("%d",&n) && n){
62         init();
63         dfs(table,1,n);
64         printf("%dn",Min);
65     }
66     return 0;
67 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!