复制书稿（book）（⼆分，贪⼼+dp）
复制书稿(book)
时间限制: 1 Sec  内存限制: 128 MB
提交: 3  解决: 1
[][][][命题⼈:]
题⽬描述
现在要把m本有顺序的书分给k个⼈复制（抄写），每⼀个⼈的抄写速度都⼀样，⼀本书不允许给两个（或以上）的⼈抄写，分给每⼀个⼈的书，必须是连续的，⽐如不能把第⼀、第三和第四本书给同⼀个⼈抄写。
现在请你设计⼀种⽅案，使得复制时间最短。复制时间为抄写页数最多的⼈⽤去的时间。
输⼊
第⼀⾏两个整数m，k；（k≤m≤500）
第⼆⾏m个整数，第i个整数表⽰第i本书的页数。
输出
共k⾏，每⾏两个整数，第i⾏表⽰第i个⼈抄写的书的起始编号和终⽌编号。k⾏的起始编号应该从⼩到⼤排列，如果有多解，则尽可能让前⾯的⼈少抄写。
样例输⼊
9 3
1 2 3 4 5 6 7 8 9
样例输出
1 5
6 7
8 9
提⽰
⼀开始直接⽤dp，但是发现这道题具有后效性，不能有dpcstring转为int
典型测试数据：
10 4
1 1 1 1 1 1 1 1 1 1
答案为
1 1
2 4
5 7
8 10
⽤dp的话答案为:
1 2
3 4
5 7
8 10
因为考虑钱4个时，dp【4】【2】最优就是 1 2  和3 4，但是因为k⾏的起始编号应该从⼩到⼤排列，如果有多解，则尽可能让前⾯的⼈少抄
写，导致，之后发现最多为3是，为了让1号是，1号应为1 ，第⼆个⼈⼲3个WA的错误解法：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<deque>
#include<stack>
#define inf 0x3f3f3f3f
using namespace std;
int a[505];
int sum[505];
int dp[505][505];
int main()
{
int m,k;
scanf("%d %d",&m,&k);
sum[0]=0;
memset(dp,inf,sizeof(dp));
for(int i=1;i<=m;i++)
{
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
dp[i][1]=sum[i];
}
for(int i=2;i<=m;i++)
{
for(int j=1;j<=i;j++)
{
for(int p=1;p<=min(i-1,k-1);p++)
{
if(dp[i][p+1]>max(dp[j][p],sum[i]-sum[j]))
{
dp[i][p+1]=max(dp[j][p],sum[i]-sum[j]);
}
}
}
}
int t=m;
int p=k;
stack<int>s;
while(!s.empty()) s.pop();
s.push(m);
while(p!=1)
{
for(int j=1;j<=t;j++)
{
if(dp[t][p]==max(dp[j][p-1],sum[t]-sum[j]))
{
s.push(j+1);
s.push(j);
t=j;
p--;
break;
}
}
}
s.push (1);
for(int i=1;i<=k;i++)
{
cout<&p()<<"";
s.pop();
cout<&p()<<endl;
s.pop();
}
//cout<<dp[m][k]<<endl;
return0;
}
View Code
因为书是不能排序的，所以单调处理，DP死套路：
1、问什么设什么：
f[i][j]表⽰前 i 本书分给 j 个⼈，
2、做过5题以上DP的⼩弱都应该想到，需要第三重循环，我设 k ⽤来表⽰*最后⼀个⼈拿的第⼀本书的编号*
k枚举的范围就是（j->i）：因为前⾯最少要保留 j-1本书分给前⾯的 j-1个⼈，最后⼀个⼈⾃⼰最少也要有⼀本，所以右边边界就是 i
3、到这⾥已经可以把最优解（每⼈分到的书页的上限）求出来，然后就懵笔了。去翻题解，原来离成功只差⼀步贪⼼。从后往前（题⽬说要前⾯的⼈尽可能没那么累），把书扔给各个⼈就A了。
还有⼀些过程中的坑，代码⾥⾯告诉你。
解法⼀：基本思路：DP⽅程求出最长花费的时间，然后⽤贪⼼的⽅法，从后向前递归，让后⾯的⼈尽量复制多的书，再倒序输出就可以了。
#include<cstdio>
#include<cstring>
int f[510][510];// f[i][j] 表⽰把前 i本书分给 k 个⼈
int ma[510],su[510];
int n,m;
int maxx(int x,int y) { return x>y?x:y; }
int minn(int x,int y) { return x<y?x:y; }
void ff()
{
for(int j=2;j<=m;j++)
{
for(int i=j;i<=n;i++)
{
for(int k=j;k<=i;k++)//k 为最后⼀个⼈拿到的第⼀本书的编号
{
int an=0;
an=maxx(f[k-1][j-1],su[i]-su[k-1]);
f[i][j]=minn(f[i][j],an);
}
}
}
}
void pr(int l,int r) //打印当前左右边界内的部分
{
int ss=0;
for(int i=r;i>=l;i--)
{
if(ss+ma[i]>f[n][m])
{
pr(l,i);
printf("%d %d\n",i+1,r);//逆序输出，回溯时才打印
return ;
}
ss+=ma[i];
}
printf("%d %d\n",1,r);//关于第⼀个⼈的特殊处理（边界）
}
int main()
{
memset(su,0,sizeof(su));//预处理前 N 项和的数组
memset(f,63,sizeof(f));
scanf("%d %d",&n,&m); if(n==0) return0;
for(int i=1;i<=n;i++)
{
scanf("%d",&ma[i]);
su[i]=ma[i]+su[i-1];
f[i][1]=su[i];
}
ff();
//printf("%d\n",f[n][m]);
pr(1,n);
return0;
}
View Code
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<deque>
#include<stack>
#define inf 0x3f3f3f3f
using namespace std;
int a[505];
int sum[505];
int dp[505][505];
int main()
{
int m,k,i,j;
scanf("%d %d",&m,&k);
sum[0]=0;
memset(dp,inf,sizeof(dp));
for( i=1;i<=m;i++)
{
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
dp[i][1]=sum[i];
}
for(i=2;i<=m;i++)
{
for(j=1;j<=i;j++)
{
for( int p=1;p<=min(i-1,k-1);p++)//记录⼏个⼈了，不能超过k个            {
if(dp[i][p+1]>max(dp[j][p],sum[i]-sum[j]))
{
dp[i][p+1]=max(dp[j][p],sum[i]-sum[j]);
}
}
}
}
int ss=dp[m][k];
//接下来⽤贪⼼的⽅法输出
stack<int>s;
while(!s.empty ()) s.pop();
int r=m,l=m;//分别表⽰两端点
int he=0;
int num=0;
for(i=m;i>=1;i--,l--)
{
he+=a[i];
if(he>ss)
{
s.push(r);
s.push(l+1);
he=a[i];
r=i;
l=i;
num++;
if(num+i==k&&(l==r)) break;
/
/每⼈只能分⼀本书了
//这边要判⼀下
//5 4 1 1 1 1 1
}
}
if(i!=0)
{//特殊情况
for(int j=i;j>=1;j--)
{
s.push (j);
s.push (j);
}
}
else
{
s.push(r);
s.push(l+1);
}
for(i=1;i<=k;i++)
{
cout<&p()<<"";
s.pop();
cout<&p()<<endl;
s.pop();
}
return0;
}
解法⼆：题解告诉我可以⽤⼆分来最优值
#include<cstdio>
#include<cstring>
int n,m,ans;
int a[510];
bool ch(int x)
{
int su=0,an=0;//an表⽰能分⼏个⼈
//printf("%d\n",x);
for(int i=n;i>=1;i--)
{
if(i==1) an++; //最后⼀⼈（最前⾯的）需要特殊处理
if(su+a[i]<=x)
{
su+=a[i];
}
else
{
an++;su=a[i];
}
}
if(an<=m) return1;
return0;
}
void pr(int l,int r) //打印当前左右边界内的部分