题解 P4274 【[NOI2004]小H的小屋】

· · 题解

P4274 [NOI2004]小H的小屋

考试的题，然后模拟退火成功弄到了90分。

不过当然是对着测试数据一次一次滴调玄学参数弄成的。。。

然后DP正解被集体hack了。。。

主要看的是这个巨佬的题解加上自己的一发YY：链接。

\#1:\text{DP+优化}：

据说是从O(n^5)优化到了O(n^4)，然后还很松，进化成了O(n^3)。。。

反正蛮神奇的，表示没有看懂优化。。。

有时间再填坑吧，这里主要介绍第二种做法。。。

\#2:\quad\text{贪心}：

我们知道，对于一块长度一定的矩形，将其均分，一定能得到最小面积的矩形分割方案。

证明？如下：

假设当前这个矩形长度为4x，并且矩形对角线斜率为k。

再假设我们当前要分成两个矩形，那么有两种分法：x,3x与2x,2x。

显然S_1=kx^2+9kx^2=10kx^2>S_2=4x^2+4x^2=8x^2

然后分3,4,5,...块时依次类推。

于是得证。

当然还可以用不等式证明，比这个更严谨，不过为了通俗易懂我就这么做了。

然后就可以贪心了。

当n \% m==0时，直接均分南北墙就是最优值。

而当n \% m>0时，应该使其余数尽量均分在每一段上。

所以此时整个图形可以分为2段：

前段有m-n \% m块北墙草坪，每段对应\lfloor\frac{n}{m}\rfloor块南墙草坪；

后段有n \% m块北墙草坪，每段对应\lfloor\frac{n}{m}\rfloor+1块南墙草坪。

所以可以枚举两段长度，取最小面积。

并且对于其中一段，其分配的面积也应该平均分配，如果余数不为0，也要把余数再平均分配。

然后，我们发现：枚举的长度对应的面积是单峰的！

所以当发现一个长度对应的面积大于当前最优解就可以直接跳出循环输出答案了。

然后就做完了。

时间复杂度是O(100)，跑的飞起。。。

记得到本蒟蒻的博客里逛逛哦！（那个DP的更新可能会贴在这里。）

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define MAXN 110
using namespace std;
int n,m,lnorth,rnorth,lsouth,rsouth;
double k1,k2,ans=(1LL<<62);//记得开最大最
inline double square(int x){return 1.00*x*x;}
inline double min(double x,double y){return x<y?x:y;}
inline double Area(int num,int len,double k){//求出面积
    if(!num)return 0;//记得特判，防止除0！
    double s=square(len/num)*k*(num-len%num)+square(len/num+1)*k*(len%num);
    return s;
}
void work(){
    if(n%m==0){//第一种情况，直接特判掉就好
        ans=Area(lnorth,100,k1)+Area(lnorth*lsouth,100,k2);
        printf("%.1lf\n",ans);
        return;
    }
    for(int i=lnorth*lsouth;i<=100-rnorth*rsouth;i++){
        double area=Area(lnorth,i,k1)+Area(rnorth,100-i,k1)+Area(lnorth*lsouth,i,k2)+Area(rnorth*rsouth,100-i,k2);
        if(ans>area)ans=area;//更新答案
        else break;//运用单调性
    }
    printf("%.1lf\n",ans);
}
void init(){
    scanf("%lf%lf%d%d",&k1,&k2,&m,&n);
    lnorth=m-n%m;rnorth=n%m;
    lsouth=n/m;rsouth=n/m+1;//求出前段与后段的南北墙的草地块数
}
int main(){//主函数So easy!
    init();
    work();
    return 0;
}