复制书稿（动态规划经典题）

水深无声 2022-06-10 10:06 230阅读 0赞

Problem Description  
现在要把m本有顺序的书分给k个人复制(抄写)，每一个人的抄写速度都一样，一本书不允许给两个(或以上)的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三和第四本书给同一个人抄写。  
现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。  
Input  
输入有多组数据，每组数据第1行两个整数m,k(k<=m<=500)；  
第2行m个整数，第i个整数表示第i本书的页数。  
Output  
对于每组数据输出k行，每行两个整数，第i行表示第i个人抄写的书的起始编号和终止编号。k行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。  
Sample Input  
9 3  
1 2 3 4 5 6 7 8 9  
Sample Output  
1 5  
6 7  
8 9  
  
Hint

如果m=k=0，则输出空行

解题思路：

![20170816154012889][]

最短时间为抄写页数最多的时间，所以要先求最多的抄写页数，从中选择最小值  
1. 设状态：f\[i\]\[j\]//将前i本书分给j个人抄写需要的最短时间；  
2. 初始状态：f\[i\]\[1\];//一个人抄写前i本书需要的最短时间就是前i本书的页数  
最终状态：f\[m\]\[k\];//将前m本书分给j个人抄写需要的最短时间  
3. 状态转移方程：先分配最后一个人抄写的页数，求得最大值 。max(f\[i-l\]\[j-1\],d\[i\]-d\[i-l\]);  
最后求最短时间 f\[i\]\[j\]=min\{max(f\[i-l\]\[j-1\],d\[i\]-d\[i-l\])\}  
  
求具体方案：  
在用动态规划求得最优值后，然后用贪心的思想，将最后一本书按逆序将书分配给k个人抄写，从第k个人开始，如果他还能写，就给他，直到分配完毕。

/*
    9 3
    1 2 3 4 5 6 7 8 9
    */
     
    #include<iostream>
    using namespace std;
    int i,j,x,y,m,n,k,t,l;
    int a[501];//存储每本书的页数
    int f[501][501];//f[i][j]表示前i本书分给j个人抄写的最短复制时间
    int d[501];//d[j]表示前j本书的总页数
    int print(int i,int j)
    {
    	int t,x;
    	if(j==0) return 0;
    	if(j==1) 
    	{
    		cout<<1<<" "<<i<<endl;
    		return 0;
    	}
    	t=i;
    	x=a[i];
    	while(x+a[t-1]<=f[m][k])
    	{
    		x=x+a[t-1];
    		t--;
    	}
    	print(t-1,j-1);
    	cout<<t<<" "<<i<<endl;
    }
    int main()
    {
    	cin>>m>>k;
    	for(i=0;i<=500;i++)
    	{
    		for(j=0;j<=500;j++)
    		{
    			f[i][j]=10000000;//对f[i][j]进行初始化 
    		}
    	}	
    	for(i=1;i<=m;i++)
    	{
    		cin>>a[i];
    		d[i]=d[i-1]+a[i];
    		f[i][1]=d[i];//把前i本书都分给1个人抄写需要的最短时间 
    	}
    //	for(i=1;i<=m;i++) cout<<d[i]<<" ";
    //	cout<<endl;
    	//f[0][0]=0;
    	for(j=2;j<=k;j++)//j个人  
    	{
    		for(i=1;i<=m;i++)//i本书 
    		{
    			for(l=1;l<=i-1;l++)//最后一个人抄写的页数
    			{
    				if(max(f[i-l][j-1],d[i]-d[i-l])<f[i][j])
    					f[i][j]=max(f[i-l][j-1],d[i]-d[i-l]);
    			} 
    		}
    	}
    	//cout<<f[m][k]<<endl; 
    	print(m,k);
    }

![20170816162627086][]

#include<iostream>
    using namespace std;
    int a[501];//a[i]表示第i本书的页数 
    int f[501][501];//f[i][j]表示前j本书分给i个人抄写需要的最短时间 
    int d[501];
    int k,m,t,x,i,j,l;
    int print(int i,int j)//输出具体方案，i本书，j个人 
    {
    	int t,x;
    	if(j==0) return 0;//递归终止条件 
    	if(j==1)
    	{
    		cout<<1<<" "<<i<<endl;
    		return 0;
    	}
    	t=i;x=a[i];
    	while(x+a[t-1]<=f[k][m])//从最后一本书开始分配，直到不能分配为止 
    	{
    		x=x+a[t-1];
    		t--;
    	}
    	print(t-1,j-1);
    	cout<<t<<" "<<i<<endl;
    }
    
    int main()
    {
    	cin>>m>>k;
    	for(i=0;i<=500;i++)
    	{
    		for(j=0;j<=500;j++)
    		{
    			f[i][j]=100000000;
    		}
    	}
    	for(j=1;j<=m;j++)
    	{
    		cin>>a[j];
    		d[j]=d[j-1]+a[j];
    		f[1][j]=d[j];
    	}
    	for(i=2;i<=k;i++)
    	{
    		for(j=1;j<=m;j++)
    		{
    			for(l=1;l<=j-1;l++)
    			{
    				if(max(f[i-1][l],d[j]-d[l])<f[i][j]) f[i][j]=max(f[i-1][l],d[j]-d[l]);
    			}
    		} 
    	}
    	//cout<<f[k][m]<<endl;
    	print(m,k);	
    }

[20170816154012889]: /images/20220610/5de009c7591d460e82219c13a494d0c2.png
[20170816162627086]: /images/20220610/37a9e3324d7945e9a6d171bbb91f0ae3.png