【习题 7-5 UVA-690】Pipeline Scheduling
习题 UVa Pipeline
2023-09-14 09:03:45 时间
【链接】 我是链接,点我呀:)
【题意】
【题解】
一定在这里写完思路再敲代码!!!处理出5个工作单元在哪些时刻会被用到。
->设为initstatu
因为每次都会面临之前已经用了一段程序,而现在要走下一步的情况
->但有一些地方是肯定已经不能走了的。
->我们可以预处理出来哪些地方是可以走的。
->剩下的.可能不能走.我们再额外处理就好
->这样可以节省很多的时间。
然后在搜索的时候.维护长度为n的statu.
(即不断更新末尾那一段,哪个时间是不能用的->有冲突的
假设要在偏移量为i的地方开始下一个程序。
直接看看statu>>i 和initstatu的and值是不是大于0.
(是一个5维的statu
等于0就说明可以放
然后更新状态。
statu = (statu>>i)&(initstatu);
【代码】
#include <bits/stdc++.h>
using namespace std;
const int N = 20+5;
int initstatu[10],n,nowstatu[10],ans = 1e8;
int can[N];
char s[N];
bool ok(int *nowstatu,int d){
for (int i = 1;i <= 5;i++){
if ((nowstatu[i]>>d)&initstatu[i]) return false;
}
return true;
}
void dfs(int dep,int s){
if (s+n>ans) return;
if (dep > 10){
ans = min(ans,s+n);
return;
}
if (s+n+(10-dep)*can[1]>ans) return;
int tempstatu[10];
for (int d = 1;d <= can[0];d++){
if (!ok(nowstatu,can[d])) continue;
//ok
//getnewstate
for (int i = 1;i <= 5;i++) tempstatu[i] = nowstatu[i];
for (int i = 1;i <= 5;i++) nowstatu[i] = (nowstatu[i]>>can[d])|initstatu[i];
dfs(dep+1,s+can[d]);
for (int i = 1;i<= 5;i++) nowstatu[i] = tempstatu[i];
}
}
int main(){
#ifdef LOCAL_DEFINE
freopen("rush_in.txt", "r", stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0);
while (cin >> n && n){
memset(initstatu,0,sizeof initstatu);
for (int i = 1;i <= 5;i++){
cin >> (s+1);
int now = 1;
for (int j = 1;j <= n;j++){
if (s[j]=='X') initstatu[i] |= now;
now = now*2;
}
}
can[0] = 0;
for (int i = 1;i <= n;i++)
if (ok(initstatu,i)){
can[0]++;
can[can[0]] = i;
}
for (int i = 1;i <= 5;i++) nowstatu[i] = initstatu[i];
ans = n*10;
dfs(2,0);
cout << ans << endl;
}
return 0;
}
相关文章
- 【习题 4-8 UVA - 12108】Extraordinarily Tired Students
- 【习题 4-6 UVA - 508】Morse Mismatches
- 【习题 4-2 Uva201】Squares
- 【习题 8-16 UVA - 1618】Weak Key
- 【习题 8-10 UVA - 1614】Hell on the Markets
- 【习题 8-6 UVA - 1611】 Crane
- 【习题 8-4 UVA - 11491】Erasing and Winning
- 【习题 7-4 UVA-818】Cutting Chains
- 【习题5-5 UVA-10391】Compound Words
- 习题 11.2 将例11.2的程序片断补充和改写成一个完整、正确的程序,用私有继承方式。在程序中应包括输入数据的函数,在程序运行时输入num,name,sex,age,addr的值,程序应输出以上。。
- 习题 7.16 写一个函数,输入一个十六进制数,输出相应的十进制数。
- 习题 8.4 有n个整数,使前面各数顺序向后移m个位置,最后m个数变成最前面m个数,见图8.43。写一函数实现以上功能,在主函数中输入n个整数和输出调整后的n个数。
- 习题 6.1 用筛选法求100之内的素数。
- 习题5.6 15红球和15个绿球排成一圈,从第1个球开始数,当数到第13个球时就拿出此球,然后再从下一个球开始数,当再数到第13个球时又取出此球,如此循环进行,直到仅剩15个球为止,问怎样排法才。。。
- 高等数学(第七版)同济大学 习题1-7 个人解答
- Java刷题面试系列习题(十三)
- Java刷题面试系列习题(四)