社区讨论
《经典》习题解答上的代码是不是有问题
UVA690 流水线调度 Pipeline Scheduling参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lo3fqn0q
- 此快照首次捕获于
- 2023/10/24 05:54 2 年前
- 此快照最后确认于
- 2023/10/24 05:54 2 年前
即陈锋的《算法竞赛入门经典习题与解答》 绿书,里面这道题没考虑一个任务同一时刻能占两个单元的情况
然而我改了一下还是过不去()所以还是求调()
CPP#include <iostream>
#include <cstdio>
#include <vector>
#include <cassert>
using namespace std;
const int maxn=20+1, UNIT=6, maxp=10;
int sys[UNIT][maxn*maxn], ansf[maxp+2];
vector<int> task[maxn];
vector<int> dist; int n;
inline bool canPut(int clock) {
// 能否在clock时间安排一个任务
for(int i=1; i<=n; i++) for(int j=0;j<task[i].size();j++) if(sys[task[i][j]][clock+i]) return false;
return true;
}
inline void put(int clock) {
for(int i=1; i<=n; i++) for(int j=0;j<task[i].size();j++) sys[task[i][j]][clock+i]=1;
}
inline void del(int clock) {
for(int i=1; i<=n; i++) for(int j=0;j<task[i].size();j++) sys[task[i][j]][clock+i]=0;
}
void dfs(int t, int T, int clock/*last task start time*/, int& ans) {
if(t==T) {
ans=min(ans, clock+n);
return;
}
for(auto D: dist){
int nc=clock+D;
if(nc+ansf[T-t] >= ans) break;
if(canPut(nc)) {
put(nc);
dfs(t+1, T, nc, ans);
del(nc);
}
}
}
signed main() {
while(cin >> n && n!=0) {
memset(sys, 0, sizeof(sys));
for(int i=1; i<maxn; i++) task[i].clear();
memset(ansf, 0, sizeof(ansf));
dist.clear();
for(int i=1; i<=5; i++) {
for(int j=1; j<=n; j++) {
char c; cin >> c;
if(c=='X') {task[j].push_back(i);}
}
}
put(0);
for(int i=0; i<=n; i++) if(canPut(i)) dist.push_back(i);
ansf[1]=n;
for(int i=1; i<=maxp; i++) {
ansf[i]=n*i;
dfs(1, i, 0, ansf[i]);
}
cout << ansf[maxp] << endl;
}
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...