1281题解

Ajwallet · 2017-12-21 20:53:48 · 题解

思路 本题有两种做法，其一为二分答案，另一种为动态规划，在这里介绍的是动态规划。

用f[n][m]表示前n本书，m个人做时的最短时间。

动态转移方程

f[j][i]=min(f[j][i],max(f[l][i-1],pa[j]-pa[l]));

ps:pa为前缀和

代码

#include<cstdio>
#define k freopen//文件输入输出
#define r(i,a,b) for(int i=a;i<=b;i++)//循环
#define pk putchar(32)//空格
#define ph putchar(10)//换行
using namespace std;int n,m,f[501][501],pa[501];//Prefix and 前缀和 
int max(int x,int y)//最大值
{
    return x>y?x:y;
}
int min(int x,int y)//最小值
{
    return x<y?x:y;
}
void read(int &a)//输入流
{
    char c;int d=1,f=0;
    while (c=getchar(),c<'0'||c>'9') if (c=='-') d=-1;f=f*10+c-48;//因为这个卡了半天，书本页数竟然有负数。。。
    while (c=getchar(),c>='0'&&c<='9') f=f*10+c-48;
    a=d*f;return;
}
void write(int x)//输出流
{
    if(x)write(x/10);else return;
    putchar(x%10+48);
}
void print(int i,int j)//输出每个人从哪抄到哪
    int t,x;
    if (i<=0) return;
    if (!j)     return;
    if(j==1)
     {write(1);pk;write(i);ph;return;}
    t=i;x=pa[i]-pa[i-1];
    while (x+pa[t-1]-pa[t-2]<=f[n][m]&&t>1)
    {
     x=x+pa[t-1]-pa[t-2];
     t--;
    }
    print(t-1,j-1);
    write(t);pk;write(i);if (i!=n) ph;
}
int main()
{
    read(n);read(m);int x;
    r(i,0,500)
     r(j,0,500)
      f[i][j]=2147483647;//初值
    r(i,1,n) {read(x);pa[i]=pa[i-1]+x;f[i][1]=pa[i];}//第一个人抄的就是前缀和
    r(i,2,m)
     r(j,1,n)
      r(l,1,j-1)
       f[j][i]=min(f[j][i],max(f[l][i-1],pa[j]-pa[l]));//动态转移
  print(n,m);//输出
  //write(f[n][m]);可以用来理解
}