bzoj1505 [NOI2004]小H的小屋 [NOI2004]小H的小屋

Time Limit: 5 Sec Memory Limit: 64 MB

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

下午有点困~~~
(dp[i][j][k]) 表示上面 (i) 个矩形, 下面 (j) 个矩形，总长度为 (k);
转移怎么暴力怎么来。
(dp[i][j][k] = min{dp[i-1][j - t][k - w] + 上面剩下的 + 下面的用t的最优解})
稍微优化一下就好了。
需要说的就是显然矩形的大小顺序没有影响，规定从大到小。
然后预处理一些需要的东西，循环里面的条件稍微多限制一下就过了。
好困啊，周围的人都在开车，我可能去了趟车展，要被安利好车推荐了。。。。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
double k1, k2;
int m, n;
double dp[maxn][maxn][maxn], pre[maxn][maxn];

inline void prepare()
{
	for(int i = 1; i <= 100; ++i)
		for(int j = 1; j <= i; ++j)
			pre[i][j] = k2 * (i / j) * (i / j) * (j - i % j) + k2 * (i / j + 1) * (i / j + 1) * (i % j);
	for(int i = 0; i <= 100; ++i)
		for(int j = 0; j <= 100; ++j)
			for(int k = 0; k <= 100; ++k)
				dp[i][j][k] = 100000000.0;
}

inline void workk()
{
	dp[0][0][0] = 0;
	for(int k = 1; k <= 100; ++k)
		for(int i = 1; i <= m && i <= k; ++i)
			for(int j = i; j <= n && j <= k; ++j)
				for(int w = 1; w <= k / i; ++w)
					for(int t = 1; t <= w && t <= j; ++t)
						dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - t][k - w] + pre[w][t] + k1 * w * w);
			
}

int main()
{
	scanf("%lf%lf%d%d", &k1, &k2, &m, &n);
	prepare();
	workk();
	printf("%.1lf", dp[m][n][100]);
	return 0;
}