【SSL】1203书的复制(normal)

Time Limit:1000MS

Memory Limit:65536K

Description

现在要把m本有顺序的书分给k个人复制（抄写），每个人的抄写速度都一样，一本书不允许分给两个或两个以上的人抄写，分给每个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。

现在请你设计一种方案，使得复制时间最短。复制时间为抄写最多的人用去的时间。

Input

第一行两个整数，m,k(k<=m<=500)

第二行为m个整数，第i个数表示第i本书的页数。

Output

最短时间

Sample Input

9 3

1 2 3 4 5 6 7 8 9

Sample Output

思路

设f[i][j]表示前i本书交由j个人抄写需要的最短时间，则状态转移方程为：

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

1<=i<=n,1<=j<=k,1<=l<j

代码

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
            using namespace std;int n,k,a[1010],f[1010][1010],sum[1010];void input(){ int i; scanf("%d%d",&n,&k); for(i=1;i<=n;i++) { scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i];//预处理前缀和 f[1][i]=sum[i]; } return;}void DP(){ int i,j,l; for(i=2;i<=k;i++) { for(j=1;j<=n;j++) { f[i][j]=100000000; for(l=1;l

上一篇：【SSL】1644取数字问题

下一篇：【SSL】1055能量项链(环形矩阵相乘)

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！