社区讨论

《经典》习题解答上的代码是不是有问题

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 条回复,欢迎继续交流。

正在加载回复...