JZOJ 3.10 1541——书架

本文主要是介绍JZOJ 3.10 1541——书架，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

当FJ不在为奶牛挤奶、打包包裹、将他的奶牛排成一队、或是砌栅栏的时候，他喜欢坐着看一本好书。多年来他收集了N(1 <= N <= 2,000)本书，他想建立一套新的书架来保存他的书。

每本书宽W(i)，高度为H(i)。书需要被按照顺序地放进书架，比如：第一个书架放了k本书，那应该是第1本到第k本，第二个书架放的书应该以第k+1本开始。每个书架可以存放宽度和至多为L(1 <= L <=1,000,000,000)的书，这个书架的高度应该是他所放的书中最高的一本书的高度。整套书架的高度为每个书架高度之和。每本书应该垂直的放在书架里。

请帮助FJ计算这套书架最小可能的高度值。

输入

第1行：两个用空格隔开的整数：N, L

第2行至第n + 1行：第i +１行有两个用空格隔开的整数：H(i), W(i)

   (1 <= H(i) <= 1,000,000; 1 <= W(i) <= L)

输出

一行，这套书架最小可能的高度值。

样例输入

5 10

5 7

9 2

8 5

13 2

3 8

样例输出

21

---

纯dp，~~暴力不会搜，DP出奇迹~~
设sum[i]为从1到i的宽度
m[i,j]为从i到j的最高的书的值
f[i]为到第i本书的最小可能高度
动态转移方程为f[i]:=min(f[j]+m[j+1,i],f[i])
1<=i<=n;
0<=j<=i

---

代码如下：

var n,l,i,j:longint;sum,h,w,f:array[0..2000]of longint;m:array[0..2000,0..2000]of longint;function min(a,b:longint):longint;
beginif a<b then exit(a) else exit(b);
end;function max(a,b:longint):longint;
beginif a>b then exit(a) else exit(b);
end;beginassign(input,'bookshelf.in');assign(output,'bookshelf.out');reset(input);rewrite(output);readln(n,l);for i:=1 to n dobeginreadln(h[i],w[i]);sum[i]:=sum[i-1]+w[i];end;for i:=1 to n dobeginm[i,i]:=h[i];for j:=i+1 to n do m[i,j]:=max(m[i,j-1],h[j]);end;for i:=1 to n do f[i]:=maxlongint div 5;f[0]:=0;for i:=1 to n dobeginfor j:=0 to i-1 doif sum[i]-sum[j]<=l then f[i]:=min(f[j]+m[j+1,i],f[i]);end;write(f[n]);close(input);close(output); 
end.

这篇关于JZOJ 3.10 1541——书架的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---