[bzoj 1505][NOI2004]小H的小屋

Description

小H发誓要做21世纪最伟大的数学家。他认为,做数学家与做歌星一样,第一步要作好包装,不然本事再大也推不出去。为此他决定先在自己的住所上下功夫,让人一看就知道里面住着一个“未来的大数学家”。 为了描述方便,我们以向东为x轴正方向,向北为y轴正方向,建立平面直角坐标系。小H的小屋东西长为100Hil(Hil是小H自己使用的长度单位,至于怎样折合成“m”,谁也不知道)。东墙和西墙均平行于y轴,北墙和南墙分别是斜率为k1和k2的直线,k1和k2为正实数。北墙和南墙的墙角处有很多块草坪,每块草坪都是一个矩形,矩形的每条边都平行于坐标轴。相邻两块草坪的接触点恰好在墙上,接触点的横坐标被称为它所在墙的“分点”,这些分点必须是1到99的整数。 小H认为,对称与不对称性的结合才能充分体现“数学美”。因此,在北墙角要有m块草坪,在南墙角要有n块草坪,并约定m≤n。如果记北墙和南墙的分点集合分别为X1,X2,则应满足X1 X2,即北墙的任何一个分点一定是南墙的分点。 由于小H目前还没有丰厚的收入,他必须把草坪的造价降到最低,即草坪的占地总面积最小。你能编程帮他解决这个难题吗?

Input

仅一行,包含4个数k1,k2,m,n。k1和k2为正实数,分别表示北墙和南墙的斜率,精确到小数点后第一位。m和n为正整数,分别表示北墙角和南墙角的草坪的块数。

Output

一个实数,表示草坪的最小占地总面积。精确到小数点后第一位。 2≤m≤n≤100 南北墙距离很远,不会出现南墙草坪和北墙草坪重叠的情况

Sample Input

0.5 0.2 2 4

Sample Output

3000.0

HINT

Solution

我的智商已经低到连矩形面积都不会算了QQ图片20160623113042

对于如题所描述的矩形,如果底边长为L,那么他的面积为L^{2}\times K

证明:记宽为R

那么由斜率的定义可知,K=R/L

R=L\times K

所以S=L\times R=L\times L\times K=L^{2}\times K

故得证

知道这个姿势以后dp方程就很好推辣

g[i,j]表示在南方向上,长度为i的区间划分出j个符合题意矩形的最小面积总和

f[i,j,k]表示长度为i的区间北方向划分出j个符合题意的矩形,南方向划分出k个符合题意的矩形的最小面积总和

容易推出

\left\{\begin{matrix}g[i,j]=min\begin{Bmatrix}g[k,j]+(i-k)^{2}k2\end{Bmatrix}\\f[i,j,k]=min\begin{Bmatrix}f[s,j-1,t]+(i-s)^{2}k1+g[i-s,k-t]\end{Bmatrix}\end{matrix}\right.

时间复杂度O(n^{3}+n^{5})

这样会TLE

但是我们发现,为了让块的面积尽可能小,那么就要一个区间内尽可能分多一点矩形

所以如果f[i,j,k]f[s1,j-1,t1]推来,f[s1,j-1,t1]f[s2,j-2,t2]推来,那么一定满足s2\leq s1,t2\leq t1,所以枚举决策就没必要从1开始

这样常数得到大大提升,能过这道题。

 

发表评论