【NOI2004】 小H的小屋
题目描述
小H的小屋 【问题描述】 小H发誓要做21世纪最伟大的数学家。他认为,做数学家与做歌星一样,第一步要作好包装,不然本事再大也推不出去。为此他决定先在自己的住所上下功夫,让人一看就知道里面住着一个“未来的大数学家”。 为了描述方便,我们以向东为x轴正方向,向北为y轴正方向,建立平面直角坐标系。小H的小屋东西长为100Hil(Hil是小H自己使用的长度单位,至于怎样折合成“m”,谁也不知道)。东墙和西墙均平行于y轴,北墙和南墙分别是斜率为k1和k2的直线,k1和k2为正实数。北墙和南墙的墙角处有很多块草坪,每块草坪都是一个矩形,矩形的每条边都平行于坐标轴。相邻两块草坪的接触点恰好在墙上,接触点的横坐标被称为它所在墙的“分点”,这些分点必须是1到99的整数。 小H认为,对称与不对称性的结合才能充分体现“数学美”。因此,在北墙角要有m块草坪,在南墙角要有n块草坪,并约定m≤n。如果记北墙和南墙的分点集合分别为X1,X2,则应满足X1X2,即北墙的任何一个分点一定是南墙的分点。 由于小H目前还没有丰厚的收入,他必须把草坪的造价降到最低,即草坪的占地总面积最小。你能编程帮他解决这个难题吗? 【输入文件】 仅一行,包含4个数k1,k2,m,n。k1和k2为正实数,分别表示北墙和南墙的斜率,精确到小数点后第一位。m和n为正整数,分别表示北墙角和南墙角的草坪的块数。 【输出文件】 一个实数,表示草坪的最小占地总面积。精确到小数点后第一位。 【约定】 2≤m≤n≤100 南北墙距离很远,不会出现南墙草坪和北墙草坪重叠的情况 【样例输入】 0.5 0.2 2 4 【样例输出】 3000.0 【评分标准】 对于每个测试点,如果你的结果与标准答案的误差不超过0.1,则可以得到该测试点的满分,否则得0分。
解法1:朴素DP+边界优化+常数优化
1 (* 2 *Problem: NOI2004 小H的小屋 3 *Author : Chen Yang 4 *Time : 2012.6.11 10:00 am 5 *State : AC 6 *Memo : 朴素DP+边界优化+常数优化 7 *) 8 program hut; 9 const maxn=111; 10 max=100000000; 11 var 12 n,m,i,j,k,len,p:longint; 13 k1,k2:double; 14 f:array[0..maxn,0..maxn,0..maxn] of double; 15 area:array[0..maxn,0..maxn] of double; 16 a:array[0..maxn] of double; 17 //======================== 18 function min(a,b:longint):longint; inline; 19 begin if a<b then exit(a) else exit(b); end; 20 //======================== 21 begin 22 assign(input,'hut.in'); reset(input); 23 assign(output,'hut.out'); rewrite(output); 24 read(k1,k2,m,n); 25 for i:=0 to maxn do 26 for j:=0 to maxn do 27 for k:=0 to maxn do f[i,j,k]:=max; 28 for i:=0 to maxn do 29 for j:=0 to maxn do area[i,j]:=max; 30 area[0,0]:=0; 31 for len:=1 to 100 do 32 for p:=1 to n do 33 for k:=1 to len do 34 if area[len,p]>area[len-k,p-1]+k2*sqr(k) then 35 area[len,p]:=area[len-k,p-1]+k2*sqr(k); 36 for i:=1 to 100 do a[i]:=k1*sqr(i); 37 f[0,0,0]:=0; 38 for i:=1 to 100 do 39 for j:=1 to min(i,m) do 40 for k:=j to min(i,n) do 41 begin 42 for len:=1 to i do 43 for p:=1 to min(len,k) do 44 if f[i,j,k]>f[i-len,j-1,k-p]+a[len]+area[len,p] then 45 f[i,j,k]:=f[i-len,j-1,k-p]+a[len]+area[len,p]; 46 end; 47 writeln(f[100,m,n]:0:1); 48 close(input); close(output); 49 end.
解法1:DP+决策单调性优化
1 (* 2 *Problem: NOI2004 小H的小屋 3 *Author : Chen Yang 4 *Time : 2012.6.11 10:00 am 5 *State : AC 6 *Memo : 动态规划优化 7 *) 8 program hut; 9 const maxn=111; 10 max=100000000; 11 var 12 n,m,i,j,k,len,p,x:longint; 13 k1,k2:double; 14 f:array[0..maxn,0..maxn,0..maxn] of double; 15 area:array[0..maxn,0..maxn] of double; 16 a:array[0..maxn] of double; 17 //======================== 18 function min(a,b:longint):longint; inline; 19 begin if a<b then exit(a) else exit(b); end; 20 //======================== 21 begin 22 assign(input,'hut.in'); reset(input); 23 assign(output,'hut.out'); rewrite(output); 24 read(k1,k2,m,n); 25 for i:=0 to maxn do 26 for j:=0 to maxn do 27 for k:=0 to maxn do f[i,j,k]:=max; 28 for i:=0 to maxn do 29 for j:=0 to maxn do area[i,j]:=max; 30 area[0,0]:=0; 31 for len:=1 to 100 do 32 for p:=1 to n do 33 for k:=1 to len do 34 if area[len,p]>area[len-k,p-1]+k2*sqr(k) then 35 area[len,p]:=area[len-k,p-1]+k2*sqr(k); 36 for i:=1 to 100 do a[i]:=k1*sqr(i); 37 f[0,0,0]:=0; 38 for i:=1 to 100 do 39 for j:=1 to min(i,m) do 40 begin 41 x:=1; 42 for k:=j to min(i,n) do 43 begin 44 for len:=1 to i do 45 for p:=x to min(len,k) do 46 if f[i,j,k]>f[i-len,j-1,k-p]+a[len]+area[len,p] then 47 begin 48 f[i,j,k]:=f[i-len,j-1,k-p]+a[len]+area[len,p]; 49 x:=p; 50 end; 51 end; 52 end; 53 writeln(f[100,m,n]:0:1); 54 close(input); close(output); 55 end.
解法2:贪心
1 /* 2 *Problem: NOI2004 小H的小屋 3 *Author : Chen Yang 4 *Time : 2012.6.12 10:00 am 5 *State : AC 6 *Memo : 贪心 7 */ 8 #include <cstdio> 9 #define min(a,b) ((a)<(b)? (a):(b)) 10 #define sqr(x) ((x)*(x)) 11 using namespace std; 12 int n, m; 13 double k1, k2, ans = 100000000; 14 inline double area(int s, int len, double k) 15 { 16 if (!s) return 0; 17 return sqr(len/s)*k*(s-len%s)+sqr(len/s+1)*k*(len%s); 18 } 19 int main() 20 { 21 freopen("hut.in", "r", stdin); 22 freopen("hut.out", "w", stdout); 23 scanf("%lf%lf%d%d", &k1, &k2, &m, &n); 24 int lm = m-n%m, rm = n%m, ln = n/m, rn = n/m+1; 25 if (!rm) ans = area(lm,100,k1)+area(lm*ln,100,k2); else 26 for (int i=lm*ln; i<=100-rm*rn; ++i) 27 { 28 double t = area(lm,i,k1)+area(rm,100-i,k1)+area(lm*ln,i,k2)+area(rm*rn,100-i,k2); 29 if (ans>t) ans = t; else break; 30 } 31 printf("%.2lf", ans); 32 return 0; 33 }
转载于:https://www.cnblogs.com/datam-cy/archive/2012/06/12/NOI2004-hut.html