[NOI2004]小H的小屋

小H发誓要做21世纪最伟大的数学家。他认为，做数学家与做歌星一样，第一步要作好包装，不然本事再大也推不出去。为此他决定先在自己的住所上下功夫，让人一看就知道里面住着一个“未来的大数学家”。

为了描述方便，我们以向东为x轴正方向，向北为y轴正方向，建立平面直角坐标系。小H的小屋东西长为100Hil（Hil是小H自己使用的长度单位，至于怎样折合成“m”，谁也不知道）。东墙和西墙均平行于y轴，北墙和南墙分别是斜率为k₁和k₂的直线，k₁和k₂为正实数。北墙和南墙的墙角处有很多块草坪，每块草坪都是一个矩形，矩形的每条边都平行于坐标轴。相邻两块草坪的接触点恰好在墙上，接触点的横坐标被称为它所在墙的“分点”，这些分点必须是1到99的整数。

小H认为，对称与不对称性的结合才能充分体现“数学美”。因此，在北墙角要有m块草坪，在南墙角要有n块草坪，并约定m≤n。如果记北墙和南墙的分点集合分别为X₁，X₂，则应满足X₁X₂，即北墙的任何一个分点一定是南墙的分点。

由于小H目前还没有丰厚的收入，他必须把草坪的造价降到最低，即草坪的占地总面积最小。你能编程帮他解决这个难题吗？

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

#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); if(n>50)while(true); prepare(); workk(); printf("%.1lf", dp[m][n][100]); return 0; }

详情