题目链接:uva 690 - Pipeline Scheduling
题目大意:有10个任务,5个管道,每个任务需要占用不同时间的管道,给出任务所占用管道的时间,求最短需要多少时间。
解题思路:dfs+剪枝,剪枝1,将所有可以的相对位置记录。剪枝2,当当前开销加上剩余任务的最有情况仍大于ans。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 5;
const int M = 100;
int n, c, ans, w[N], jump[M];
bool judge (int* s, int k) {
for (int i = 0; i < N; i++) {
if ((s[i]>>k)&w[i]) return false;
}
return true;
}
void init () {
char str[M];
c = 0;
ans = n * 10;
memset(w, 0, sizeof(w));
for (int i = 0; i < N; i++) {
scanf("%s", str);
for (int j = 0; j < n; j++)
if (str[j] == 'X')
w[i] |= (1<<j);
}
for (int i = 0; i <= n; i++) {
if (judge (w, i)) {
jump[c++] = i;
}
}
}
void dfs (int* s, int d, int sum) {
if (sum + jump[0] * (10 - d) > ans) return;
if (d == 10) {
ans = min (ans, sum);
return;
}
for (int i = 0; i < c; i++) {
if (judge (s, jump[i])) {
int p[N];
for (int j = 0; j < N; j++)
p[j] = (s[j]>>jump[i])^w[j];
dfs (p, d + 1, sum + jump[i]);
}
}
}
int main () {
while (scanf("%d", &n), n) {
init ();
dfs (w, 1, n);
printf("%d\n", ans);
}
return 0;
}
分享到:
相关推荐
方便gltf-pipeline相关人员下载使用
资源来自pypi官网。 资源全名:bamboo-pipeline-3.6.3.tar.gz
gltf-pipeline对gltf文件进行压缩,压缩后的文件加载时需要专门的接压缩算法,这里面的js就是!包括: draco_decoder.js draco_decoder.wasm draco_encoder.js draco_wasm_wrapper.js
glTF管道 由和用来优化资产的内容流水线工具。 支持常见的操作,包括: 将glTF转换为glb(并反向) 将缓冲区/纹理保存为嵌入式文件或单独的文件 将glTF 1.0模型转换为glTF 2.0... gltf-pipeline -i model.glb -j
jenkins-common-pipeline:具有共享库的Jenkins通用管道
资源来自pypi官网。 资源全名:django-pipeline-compass-0.1.4.tar.gz
sophon-pipeline相关+边缘端设备+机器学习
Supports only Standard (Legacy) Pipeline! Looking for Universal (URP) Pipeline? It is another package: HERE New sample videos are shot with iPad (2017 model) with highest quality settings. Scene has ...
开源项目-m-reda-pipeline.zip,Pipeline: Node-based automation server
Ansible-ansible-jenkins-pipeline.zip,负责安装带有管道插件的jenkins的角色不负责的角色:带有管道的jenkins,ansible是一个简单而强大的自动化引擎。它用于帮助配置管理、应用程序部署和任务自动化。
jar包,亲测可用
jenkins-ci-pipeline-源码.rar
docker-client.zip,docker clientinactive:jvm的简单docker客户端
Algorithms-for-Real-Time-Endoscopy-Image-Processing-Pipeline-in-Clinical-Decision-Support-Systems
S3032-Advanced-Scenegraph-Rendering-Pipeline
开源项目-myntra-pipeline.zip,Pipeline: A package to build multi-staged concurrent workflows with a centralised logging output
website-metrics-pipeline-main.rar
源代码:scrapy-pipeline数据写入excel-openpyxl
Redis-PipeLine批量导入.docx
该组件本质上提供了三大功能: scheduler - 调度器 dupefilter - URL去重规则(被调度器使用) pipeline - 数据持久化 Scrapy是一个比较好用的Python爬虫框架,你只需要编写几个组件就可以实现网页数据的爬取。但是...