淘先锋技术网

首页 1 2 3 4 5 6 7

P1281 书的复制（区间dp）

luogu 链接：https://www.luogu.com.cn/problem/P1281

首先分析状态转移方程

第一行是m，k

m是书的个数，k是人的个数

这个题的决策明显在划分区间上，也就是决定哪些书给哪些人抄

则根据题设用二维数组f[i][j]表示前i个人抄前j本书的用时最小值

这样状态转移方程就呼之欲出了：

f[i][j] = min(f[i][j],max(f[i-1][k-1],sum[j]-sum[k-1]);

其中sum为前缀和数组，每次分出去一个人，自然i-1。让这个人从第k本书开始抄，那么前面花费的时间自然是抄k-1本书的时间，分出去的这个人花费的时间是从第k本书抄起的一直抄完j本所花费的时间，所以花费的时间是sum[j]-sum[k-1]。

这同时启示我们要用到前缀和数组来维护一段区间上的抄书所花费的时间。

然后考虑怎么写循环来把动态规划核心代码补充完整：

首先循环区间，再循环决策，这里的决策自然是不同的划分区间的方案

for(int i=2;i<=k;i++)    //j = 1的情况，放在初始化里
for(int j=2;j<=m;j++)   //若是只是抄第一本书，则不论多少人都是一样的结果
for(int k=2;k<=j;k++)   //k从1开始是没有意义的，因为转移方程里出现了k-1，k等于0的时候是没有意义的
f[i][j] = min(f[i][j],max(f[i-1][k-1],sum[j]-sum[k-1]);

上主函数

int main()
{
	cin>>m>>k;
	for(int i=1;i<=m;i++) 
	{
		cin>>num[i];
		sum[i] = sum[i-1]+num[i];              //初始化前缀和数组 
	}
	
	memset(f,0x3f3f3f3f,sizeof f);
	
	for(int i=1;i<=m;i++) f[1][i] = sum[i];    //初始化下面循环中i等于1的情况，此时只有一个人，所用时间就是抄全部书的时间 
	
	for(int i=1;i<=k;i++) f[i][1] = sum[1];    //初始化下面循环中j等于1的情况，此时只有一本书，来多少人都是抄一本书的时间 
	
	for(int i=2;i<=k;i++)
		for(int j=2;j<=m;j++)
			for(int k=2;k<=j;k++)
				f[i][j] = min(f[i][j],max(f[i-1][k-1],sum[j]-sum[k-1]));
				
	print(m, f[k][m]);       //最后一步贪心输出答案 
	return 0;			
}

但是得出最小抄书时间还不太行，最后要输出的是具体方案

我们想一想，题目中说了要前面的人抄的数量尽可能少，那么我们应当从后往前贪心，把后面的人“喂饱”了再考虑前面人的情况

很容易想到用递归的形式实现

void print(int x, int maxx)                //x是当前枚举的起点（从后往前），maxx是每人最多可以抄多少页书 
{
    if(!x) return;                         //为了避免死循环，让i==0进入循环的时候就应该立即return，因为这时已经枚举到终点，仅仅需要输出 
    for(int i=x; i>=0; i--) 
	{
        if(sum[x] - sum[i-1] > maxx || !i) //为了输出第一项，也就是第一个人从第一本开始抄的情况，需要让i=0进入循环，输出自然是从i+1开始的 
		{
            print(i, maxx);                //为了满足正序输出，但是是倒序循环，所以应该先递归后输出 
            printf("%d %d\n", i+1, x);
        	return;
        }
    }
}

最后来一遍完整代码⑧

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int m,k;
int num[1010]; 
int sum[1010];
int f[1010][1010];  //f[i][j]表示前i个人，j本书 
int res[10010]; 
void print(int x, int maxx)                //x是当前枚举的起点（从后往前），maxx是每人最多可以抄多少页书 
{
    if(!x) return;                         //为了避免死循环，让i==0进入循环的时候就应该立即return，因为这时已经枚举到终点，仅仅需要输出 
    for(int i=x; i>=0; i--) 
	{
        if(sum[x] - sum[i-1] > maxx || !i) //为了输出第一项，也就是第一个人从第一本开始抄的情况，需要让i=0进入循环，输出自然是从i+1开始的 
		{
            print(i, maxx);                //为了满足正序输出，但是是倒序循环，所以应该先递归后输出 
            printf("%d %d\n", i+1, x);
        	return;
        }
    }
}

int main()
{
	cin>>m>>k;
	for(int i=1;i<=m;i++) 
	{
		cin>>num[i];
		sum[i] = sum[i-1]+num[i];              //初始化前缀和数组 
	}
	
	memset(f,0x3f3f3f3f,sizeof f);
	
	for(int i=1;i<=m;i++) f[1][i] = sum[i];    //初始化下面循环中i等于1的情况，此时只有一个人，所用时间就是抄全部书的时间 
	
	for(int i=1;i<=k;i++) f[i][1] = sum[1];    //初始化下面循环中j等于1的情况，此时只有一本书，来多少人都是抄一本书的时间 
	
	for(int i=2;i<=k;i++)
		for(int j=2;j<=m;j++)
			for(int k=2;k<=j;k++)
				f[i][j] = min(f[i][j],max(f[i-1][k-1],sum[j]-sum[k-1]));
				
	print(m, f[k][m]);       //最后一步贪心输出答案 
	return 0;			
}