记录编号	287683	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]作业调度方案	最终得分	100
用户昵称	Twist Fate	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2016-08-02 10:31:26	内存使用	1.82 MiB

// NOIP 2006 第三题
//这题题目太绕了，(#‵′)靠。。
//所以讲讲题目大意，理理思路
//(1)对同一个工件，每道工序必须在它前面的工序完成后才能开始；
//(2)同一时刻每一台机器至多只能加工一个工件。
//(3)还要注意，“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时，有可能排在后面的某个操作比前面的某个操作先完成。 
//这三句话是重点，比如1-1，1-2，2-1，3-1，3-2，2-2 
//也就是说在所有第一工序中，1号肯定要the first blood，
//在所有第二工序中，一号还是一血。。。。所以。。。
//就不停更新代表机器的数组，直到处理了n*m个工序为止 
//至于主程序，就是纯模拟O__O "…
//Ｏ(≧口≦)Ｏ好难啊(=@__@=)。。
//NOIP2006作业调度
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std; 
const int  maxn=20;
int d[maxn*maxn+1];
int id[maxn+1][maxn+1],t[maxn+1][maxn+1];
int f[maxn][maxn*1000+1];
int c[maxn+1],p[maxn+1];
int k=0,now=0,temp=0,j,i;
bool flag;
int main(){
	freopen("jsp.in","r",stdin);
	freopen("jsp.out","w",stdout);
	int n,m;
	scanf("%d%d",&m,&n);//m表示机器数，n表示工件数 
	for(i=1;i<=n*m;i++)
		scanf("%d",&d[i]);
	for(i=1;i<=n;i++)	
		for(j=1;j<=m;j++)
			scanf("%d",&id[i][j]);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			scanf("%d",&t[i][j]);
		memset(f,true,sizeof(f));
	for(i=1;i<=n*m;i++){
		now=d[i];
		c[now]++;//更新工作序号
		k=p[now]+1;//纪录起点
		do{
     while(!f[id[now][c[now]]][k]) k++; //跳过无法工作区域
     flag=true;
     for(j=k;j<=k+t[now][c[now]]-1;j++) //检验是否有足够时间
       if(!f[id[now][c[now]]][j])
       {
          flag=false;
          temp=j;//记录停止时间
          break;
       }
     if(flag)
     {
       for(j=k;j<=k+t[now][c[now]]-1;j++) //将当前工作写入工作轴中
          f[id[now][c[now]]][j]=false;
       p[now]=k+t[now][c[now]]-1; //更新起点
       break;
    }
     k=temp; //假如没有足够时间则从停止时间重新开始
   }while(true);
}
	k=-1000000;
	for(i=1;i<=maxn;i++)
		k=max(k,p[i]);
	printf("%d",k);
	return 0;
}