做设计挣钱的网站/网站模板套用教程

https://vjudge.net/problem/UVA-690

 

一台计算机有5个工作单元

一个任务有n个部分，每个部分都要使用一个工作单元

一个工作单元只能同时执行一个任务的一部分

现在有10个相同的任务需要执行

问最少用时

 

二进制记录每个工作单元当前的使用情况

枚举这个任务进行到哪个部分时，下一个任务开始

 

剪枝：

1、预处理pos[i] 表示 这个任务进行到哪个部分时，下一个任务可以开始

枚举的时候，只枚举这些部分

2、假设当前是第i个任务，前i-1的任务用时为k

第i个任务进行到第j个部分时，第i+1 个任务开始

若k+j+（10-i+1）* min(pos[])>=ans return

即之后的任务都用最早时间都>=当前答案，剪掉

 

#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;int n,bin[21];int cnt,pos[21],state[5];char s[21];int ans;bool judge(int v[5],int len)
{for(int i=0;i<5;i++)if(state[i]&(v[i]>>len)) return false;return true;
}void dfs(int task,int len,int window[5])
{if(task==10) {ans=min(ans,len);return;}int tmp[5];for(int i=1;i<=cnt;i++){if(!judge(window,pos[i])) continue;if(len+pos[i]+(10-task)*pos[0]>=ans) return;memcpy(tmp,window,sizeof(tmp));for(int j=0;j<5;j++) tmp[j]=(tmp[j]>>pos[i])|state[j];dfs(task+1,len+pos[i],tmp);}
}int main()
{bin[0]=1;for(int i=1;i<=20;i++) bin[i]=bin[i-1]<<1;while(1){scanf("%d",&n);if(!n) return 0;for(int i=0;i<5;i++){scanf("%s",s); state[i]=0;for(int j=0;j<n;j++)if(s[j]=='X') state[i]|=bin[j];}cnt=0;for(int i=1;i<=n;i++) if(judge(state,i)) pos[++cnt]=i;ans=n*10;dfs(1,n,state);printf("%d\n",ans);}
}