ワークスケジュール

3、ワークスケジューリング(work.pas/c/cpp)【問題の説明】Jamの工場に新たに商品が入ってきたので、急いで加工する必要があります.工場にはたくさんの加工機械があります.これらの貨物には余裕がありますが、加工方法を合理的に手配して、各加工機械を十分に利用させたいと思っています.例えば、彼はワークを8時間以内に加工して完成させることを望んでいます.ここに5つのワークがあることが知られています.順序によって、消費する時間は次は5 2 4 4 3、つまり5つのワークが8時間以内に完成しなければならない.もちろん、それぞれ5台の加工機械で完成するようにスケジューリングすることができますが、1台の機械ごとに3 6 4 4 5時間空いているので、機械の加工利用率は低くなります.ここでは、残りの時間の二乗と、あなたがスケジューリングした加工利用率、すなわち32+62+42+42+52=102を表します.もちろん、Jamはこの値が小さいほど良いことを望んでいます.そうすれば、機械を十分に利用することができます.また、同じ機械で1つのワークを加工した後、1時間休む必要があります.ワークの加工は所定の順序で入力されますので、注意してください:1.加工の順序は所定の後のワークを前に持って加工することができなくて、図の中の2と3のように位置を変えることができなくて、順番に所定の順序でスケジューリングするしかありません.この点に注意してください.
2.休憩時間はl時間です.この例では、Jamが7時間以内に完了するように要求した場合、5番ワークは別の機械で完了しなければなりません.もちろん、Jamは最も長い時間を消費するワークよりも韻時間が長いことを保証します.そうしないと解けません. 
3.機械の数が無限であることを見ることができます.1つのスケジューリングについて、いくつかの機械加工が必要であれば、総効率が最も高く、つまり効率値が最も小さい限り.
4.いかなるワークも前に手配すべきで、ワークが完成した後にしか空き時間を残すことができなくて、この点、図の中にも体現があります. 
【入力ファイル】(work.in)
入力ファイルの1行目はJamが完成を要求した時間とワークの数2行目はそれぞれ1番ワークに必要な時間、2番ワークに必要な時間…入力順は所定の順序
【出力ファイル】(work.out)出力ファイルは2行で、第1動作が最小の効率値であり、第2行から以下がスケジューリングスキームである.
【入力サンプル】
8 5
5 2 4 4 3 
【出力サンプル】
10
5
2 4 
4 3 
【注釈】出力する方案はワークをできるだけ前にスケジューリングすること.例えば:
入力の場合
8 3
5 2
5
出力は
9 
5 2 
5 
ではなく
9
5 
2  5
【データ規模】40%のデータに対して、ワーク数<10 Jam要求時間<30 100%のデータに対して、ワーク数<500 Jam要求時間<30000データ保証効率値がロング整数範囲内
【データ規模】40%のデータに対して、ワーク数<10 Jam要求時間<30 100%のデータに対して、ワーク数<500 Jam要求時間<30000データ保証効率値がロング整数範囲内
この問題にはいろいろな解法があるようですが、試験の時の考えから話しましょう.この問題を見てまず思いついたのが区間DPです.しかし、当時は頭の悪いミスを犯してACができなかったので、試して修正したコードです.

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int i,j,k,n,m,a[503],times,sum[503][503],ans,p;
int f[503][503],g[503][503];
int s[503][503],num;
void dfs(int x,int len)//                  
{
	if (x==0||len==0)
	 return;
	dfs(x-g[x][len],len-1);
    num++; int j=0;
	for (int i=x-g[x][len]+1;i<=x;i++)
	 j++,s[num][j]=a[i];
    s[num][0]=g[x][len];
}
int main()
{
	freopen("work.in","r",stdin);
	freopen("work.out","w",stdout);
	scanf("%d%d",&times,&n);//times           ，n     
	for (i=1;i<=n;i++)
	 scanf("%d",&a[i]);
	for (i=1;i<=n-1;i++)//   sum  ，sum[i][j]   i j       
	 for (j=i;j<=n;j++)
	  sum[i][j]=sum[i][j-1]+a[j];
	<span style="background-color: rgb(255, 255, 255);"><span style="color:#6600cc;">sum[n][n]=a[n];//             ，T_T</span></span>
    memset(f,127/3,sizeof(f));
    f[0][0]=0;
    for (i=1;i<=n;i++)
     f[0][i]=0;
    for (i=1;i<=n;i++)
     if (sum[1][i]+i-1<=times)
      {
      	f[i][1]=(sum[1][i]+i-1-times)*(sum[1][i]+i-1-times);
      	g[i][1]=i;
      }
     else
      break;
	for (j=2;j<=n;j++)//         
	 for (i=j;i<=n;i++)//         
	  for (k=1;k<=i-j+1;k++)//         
	   if (sum[i-k+1][i]+k-1<=times)//                 
	   {
	   	 int t=f[i-k][j-1]+(sum[i-k+1][i]+k-1-times)*(sum[i-k+1][i]+k-1-times);
	   	 if (f[i][j]>t||f[i][j]==t&&<span style="color:#6600cc;">g[i][j]>k</span>)//      ，                     ，           
	   	  {
	   	  	f[i][j]=t; g[i][j]=k; //f[i][j]     I，  J           ，G[I][J]      ，    
	   	  }
	   }
	ans=1000000000;
	p=0;
	for (i=1;i<=n;i++)
	 if (ans>f[n][i])
	  {
	  ans=min(ans,f[n][i]);
	  p=i;
      }
	printf("%d
",ans);
	dfs(n,p);
    for (i=1;i<=num;i++)
     {
     	for (j=1;j<=s[i][0];j++)
     	 printf("%d ",s[i][j]);
     	printf("
");
     }
	return 0;
}

にはもう一つの考え方がありますが、実は理解しやすいです.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[503][503],s[503][503],len[503],loap[503];
int i,j,k,m,n,l;
void dfs(int i,int j)//                
{
	if (i==j)  l++;
	else
	 {
	 	int x;
	 	if (s[i][j]==0)
	 	 for (x=i;x<=j;x++) l++;
	 	else
	 	 {
	 	 	if (i<=s[i][j])
	 	 	 dfs(i,s[i][j]);
	 	 	loap[l+1]=1;
	 	 	if (s[i][j]+1<=j)
	 	 	 dfs(s[i][j]+1,j);
	 	 }
	 }
	
}
int main()
{
	freopen("work.in","r",stdin);
	freopen("work.out","w",stdout);
	scanf("%d%d",&m,&n);
	for (i=1;i<=n;i++)
	 scanf("%d",&len[i]),dp[i][i]=len[i],loap[i]=0;
	for (i=1;i<n;i++)
	 for (j=1;j<=n-i;j++)
	  k=i+j,dp[j][k]=dp[j][k-1]+len[k];
	for (i=0;i<n;i++)//i      ，dp[j][k]    j k       
	 for (j=1;j<=n-i;j++)
	  {
	  	k=i+j;
	  	int tmp=m-dp[j][k]-k+j;
	  	if (tmp<0)  dp[j][k]=2000000000;//    j k          
	    else  dp[j][k]=tmp*tmp;
	  }
	for (i=0;i<n;i++)
	 for (j=1;j<=n-i;j++)
	  {
	  	k=i+j;
	  	for (int l=k-1;l>=j;l--)
	  	 if (dp[j][l]<2000000000&&dp[l+1][k]<2000000000)
	  	  if (dp[j][l]+dp[l+1][k]<dp[j][k])
	  	   dp[j][k]=dp[j][l]+dp[l+1][k],s[j][k]=l;//s[j][k]      
	  }
    printf("%d
",dp[1][n]);
    l=0;
	dfs(1,n);
	for (i=1;i<=n;i++)
	 {
	 	if (loap[i]==1) printf("
");
	 	printf("%d ",len[i]);
	 }	
}

小編雲:動き回るには必ず脳がはっきりしなければならない.手が不自由な+脳が不自由ではない.もちろん考えないでください.