LINK：小H的小屋
尽管有论文 但是 其证明非常的不严谨 结尾甚至还是大胆猜测等字样...
先说贪心：容易发现m|n的时候此时均分两个地方就是最优的。
关于这个证明显然m在均分的时候的分点一定是n的子集 考虑不为均分的时候答案一块增多一个增少 但是增多的幅度显然更大 所以的证。
然后 当m不整除n的时候 容易想到还是均分的思路 不过 这次 对于一部分均分到的是 n/m 一部分是n/m+1.
然后暴力枚举中间的分点即可 然后进行计算。
这样复杂度O(100) 异常优秀。
考虑不那么优秀的dp.
容易想到 每放一块北墙对应多块南墙 设状态 f[i][j][k]表示前i块北墙j块南墙此时端点在j的最小值。
这状态转移是n^5的 不过大力跑也能A.值得注意的是 在状态转移的时候需要预处理一下数组g[i][j]表示i个南墙分j个距离的最小值。
因为题目中明确说了 分的位置必须为整数。当然直接计算也是可以依靠分成两段计算也行。可以发现那样也是最优的。
考虑优化 考虑优化j的状态转移 当k递增时 j的转移必然递增。
考虑到 如果j减小了那么造成对于更小的面积用更多的墙 这显然不是最优的。
所以此时总复杂度n^4.
值得注意的是 还可以优化 对于 i,j,k固定的时候 j,k的决策一定不会比 i+1,j,k的决策更大 所以再开个数组存上次的决策来优化转移。
这个证明不太会。
n^4的做法 显然可过嘛.
const int MAXN=310000,G=3;
int m,n;
db ans,k1,k2,s1;
db f[102][102][102];//f[i][j][k]表示 前i个北墙 前j个南墙 现在到达点k的最小面积
db g[102][102];
//int g[101][101][101][2];//g[i][j][k]表示 这个状态的最优决策
int main()
{
freopen("1.in","r",stdin);
gi(k1);//北
gi(k2);//南
gt(m);//北
gt(n);//南
//m<=n;
if(n%m==0)
{
db w2=100.0/(n*1.0);
db w1=100.0/(m*1.0);
ans=w2*k2*n*w2+w1*w1*k1*m;
printf("%.1lf\n",ans);
return 0;
}
rep(0,m,i)rep(0,n,j)rep(0,100,k)f[i][j][k]=INF;
rep(0,n,i)rep(0,100,k)g[i][k]=INF;
g[0][0]=0;
rep(1,n,i)rep(i,100,j)
rep(1,j,k)g[i][j]=min(g[i][j],g[i-1][j-k]+k*k*k2);
f[0][0][0]=0;
rep(1,m,i)//北墙
rep(i,n,j)//南墙
{
rep(j,100,k)
{
//枚举北墙的决策得到南墙的决策.
//cout<<f[i][j][k]<<endl;
int w2=1;//w2逐渐增大
rep(1,k,w1)//w1决策增大的时候 w2决策不会减小
{
while(g[w2+1][w1]+f[i-1][j-w2-1][k-w1]<f[i-1][j-w2][k-w1]+g[w2][w1]&&w2+1<=j)++w2;
//rep(1,j,w2)
f[i][j][k]=min(f[i][j][k],f[i-1][j-w2][k-w1]+g[w2][w1]+(db)w1*k1*w1);
//if(i<=1&&j<=1&&k<=10)cout<<f[i-1][j-w2][k-w1]<<' '<<f[ i][j][k]<<' '<<i<<' '<<j<<' '<<k<<' '<<w2<<' '<<j-w2<<' '<<k-w1<<endl;
}
}
}
printf("%.1lf",f[m][n][100]);
return 0;
}