注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1048】【HAOI2007】【分割矩阵】  

2014-03-13 20:16:10|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   裸的DP...首先均方差为 sqrt(∑(xi-x|)*(xi-x|)/n) ,x|为∑xi/n,即平均数。    
  然后f[i][j][k][l][w] 表示 以 (i,j)左上角,(k,l) 右下角的矩阵,分割成W份的最小的 ∑(xi-x|)*(xi-x|)     
  然后转移就是枚举割的地方和割数...
================================

program bzoj1048;
var f:array[0..10,0..10,0..10,0..10,0..10]of double;
    sum:array[0..10,0..10]of longint;
    a,b,n:longint;
    ave,ans:double;

function min(a,b:double):double;
begin
  if a<b then exit(a) else exit(b);
end;

procedure init;
var i,j,k,l,w,cut,ti:longint;
begin
  read(a,b,n);
  fillchar(sum,sizeof(sum),0);
  for i:=1 to a do
    for j:=1 to b do
     begin
      read(w);
      sum[i][j]:=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+w;
     end;
  ave:=sum[a][b]/n;
  for i:=1 to a do
   for j:=1 to b do
    for k:=i to a do
     for l:=j to b do
      begin
      f[i][j][k][l][1]:=
      sqr(sum[k][l]+sum[i-1][j-1]-sum[k][j-1]-sum[i-1][l]-ave);
      for w:=2 to n do f[i][j][k][l][w]:=1e10;
      end;
  for w:=2 to n do
   for i:=1 to a do
    for j:=1 to b do
     for k:=i to a do
       for l:=j to b do
        begin
          for cut:=i to k-1 do
           for ti:=1 to w-1 do
           f[i][j][k][l][w]:=min(f[i][j][k][l][w],
           f[i][j][cut][l][ti]+f[cut+1][j][k][l][w-ti]);
          for cut:=j to l-1 do
           for ti:=1 to w-1 do
           f[i][j][k][l][w]:=min(f[i][j][k][l][w],
           f[i][j][k][cut][ti]+f[i][cut+1][k][l][w-ti]);
        end;
  ans:=f[1][1][a][b][n]/n;
  ans:=sqrt(ans);
  write(ans:0:2);
end;

begin
  init;
end.




  评论这张
 
阅读(84)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017