/*
dp[k][x1][y1][x2][y2]:左上角坐标为(x1,y1),右下角坐标为(x2,y2)
的棋盘,设它把切割k次以后得到的k+1块矩形的总分平方和最小值.
s[x1][y1][x2][y2]:左上角坐标为(x1,y1),右下角坐标为(x2,y2)
的棋盘的总和的平方
dp[k][x1][y1][x2][y2] =
1)按横的划分: min(dp[k-1][x1][y1][f][y2]+s[f+1][y1][x2][y2]
, dp[k-1][f+1][y1][x2][y2]+s[x1][y1][f][y2]);
2)按竖的划分: min(dp[k-1][x1][y1][x2][f]+s[x1][f+1][x2][y2]
, dp[k-1][x1][f+1][x2][y2]+s[x1][y1][x2][f]);
*/
#include < iostream >
#include < cmath >
#define INF 10000000
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int m = 8 ;
int a[ 10 ][ 10 ];
int n;
double dp[ 16 ][ 10 ][ 10 ][ 10 ][ 10 ], s[ 10 ][ 10 ][ 10 ][ 10 ];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**/ /*
dp[k][x1][y1][x2][y2]:左上角坐标为(x1,y1),右下角坐标为(x2,y2)
的棋盘,设它把切割k次以后得到的k+1块矩形的总分平方和最小值.
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
s[x1][y1][x2][y2]:左上角坐标为(x1,y1),右下角坐标为(x2,y2)
的棋盘的总和的平方
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
dp[k][x1][y1][x2][y2] =
1)按横的划分: min(dp[k-1][x1][y1][f][y2]+s[f+1][y1][x2][y2]
, dp[k-1][f+1][y1][x2][y2]+s[x1][y1][f][y2]);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
2)按竖的划分: min(dp[k-1][x1][y1][x2][f]+s[x1][f+1][x2][y2]
, dp[k-1][x1][f+1][x2][y2]+s[x1][y1][x2][f]);
*/
double mmin( double a, double b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
return a < b ? a: b;
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
// freopen("data.txt", "r", std);
int x1, y1, x2, y2, t, f;
double sum, average, temp;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (cin >> n)
{
sum = 0 ;
for (x1 = 0 ; x1 < m; x1 ++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (y1 = 0 ; y1 < m; y1 ++ )
{
cin >> a[x1][y1];
sum += a[x1][y1];
}
average = sum / n;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (x1 = 0 ; x1 < m; x1 ++ )
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (y1 = 0 ; y1 < m; y1 ++ )
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (x2 = x1; x2 < m; x2 ++ )
{
sum = 0 ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (y2 = y1; y2 < m; y2 ++ )
{
sum += a[x2][y2];
if (x1 == x2)
s[x1][y1][x2][y2] = sum;
else
s[x1][y1][x2][y2] = s[x1][y1][x2 - 1 ][y2] + sum;
}
}
}
}
for (x1 = 0 ; x1 < m; x1 ++ )
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (y1 = 0 ; y1 < m; y1 ++ )
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (x2 = x1; x2 < m; x2 ++ )
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (y2 = y1; y2 < m; y2 ++ )
{
s[x1][y1][x2][y2] *= s[x1][y1][x2][y2];
dp[ 0 ][x1][y1][x2][y2] = s[x1][y1][x2][y2];
}
}
}
}
for (t = 1 ; t < n; t ++ )
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (x1 = 0 ; x1 < m; x1 ++ )
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (y1 = 0 ; y1 < m; y1 ++ )
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (x2 = x1; x2 < m; x2 ++ )
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (y2 = y1; y2 < m; y2 ++ )
{
dp[t][x1][y1][x2][y2] = INF;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (f = x1; f < x2; f ++ )
{
temp = mmin(dp[t - 1 ][x1][y1][f][y2] + s[f + 1 ][y1][x2][y2]
, dp[t - 1 ][f + 1 ][y1][x2][y2] + s[x1][y1][f][y2]);
dp[t][x1][y1][x2][y2] = mmin(temp, dp[t][x1][y1][x2][y2]);
}
for (f = y1; f < y2; f ++ )
{
temp = mmin(dp[t - 1 ][x1][y1][x2][f] + s[x1][f + 1 ][x2][y2]
, dp[t - 1 ][x1][f + 1 ][x2][y2] + s[x1][y1][x2][f]);
dp[t][x1][y1][x2][y2] = mmin(temp, dp[t][x1][y1][x2][y2]);
}
}
}
}
}
}
double ans;
ans = dp[n - 1 ][ 0 ][ 0 ][m - 1 ][m - 1 ] / n - average * average;
printf( " %.3llf\n " , sqrt(ans));
}
return 0 ;
}
posted on 2009-04-21 19:57
longshen 阅读(1575)
评论(0) 编辑 收藏 引用 所属分类:
poj