水題一道，第一次的時候不小心只得了70分。
NOIp2006中最簡單的一道題，只要簡單地模擬一下就可以了。對于這道題關鍵在于仔細閱讀題目，題目變態地長！細心再細心！
用last[i]記錄第i個工件目前為止需要的時間，后面的工序在此基礎上添加就可以了。最后掃描一遍last[i]數組，最大的那個即為最終答案。
數據規模很小，基本不涉及什么復雜度的問題。
一開始做的時候忘了在ok()函數中的那個循環的條件中減去1，調試的時候下面的改了過來上面的忘記了……
以下是我的代碼：
#include<stdio.h>
long m,n,order[450],num[21][21],time[21][21];
long ans,d[21][450]=
{0},last[21]={0},count[21]={0};
int ok(long nn,long ss,long begin)
{// 第nn個工件的第ss個工序可以在begin時間加工
long i,tmp=num[nn][ss];// 在第tmp個機器上加工
for(i=begin;i<=begin+time[nn][ss]-1;i++)
if(d[tmp][i]==1)
return 0;
return 1;
}
int main()
{
FILE *fin,*fout;
long i,j,k,t1,t2;
fin=fopen("jsp.in","r");
fscanf(fin,"%ld%ld",&m,&n);
for(i=1;i<=m*n;i++)
fscanf(fin,"%ld",&order[i]);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
fscanf(fin,"%ld",&num[i][j]);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
fscanf(fin,"%ld",&time[i][j]);
fclose(fin);
// Read In
for(i=1;i<=m*n;i++)
{
t1=order[i];// 第t1個工件
count[t1]++;// order[i]的第count件工序
t2=num[t1][count[t1]];// 在第t2個機器上加工
for(k=last[t1]+1; ;k++)
if(ok(t1,count[t1],k))
{
for(j=k;j<=k+time[t1][count[t1]]-1;j++)
d[t2][j]=1;
break;
}
last[t1]=k+time[t1][count[t1]]-1;
}
ans=0;
for(i=1;i<=n;i++)
if(ans<last[i])
ans=last[i];
fout=fopen("jsp.out","w");
fprintf(fout,"%ld\n",ans);
fclose(fout);
return 0;
}
posted on 2010-01-06 19:49
lee1r 閱讀(466)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：基礎/模擬