棋盘分割（NOI99）
Chessboard Division
Chess.{pas|bas|c}
Chess.exe
将一个８×８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)
原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。
请编程对给出的棋盘及n，求出均方差σ的最小值。
输入
第1行为一个整数n(1
第2行至第9行每行为8个小于100的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。
输出
仅一个数，为σ（四舍五入精确到小数点后三位）。
样例输入
3
1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 3
样例输出
1.633
题解
现在NOI的题做起来还是很费事……那个sigma的式子的化简则完全是参照lrj的牛书完成的，好失败……
中间调试了相当一段时间，都是由于些弱智错误……囧
#include <fstream>
#include <cassert>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("chess.in");
ofstream fout("chess.out");
int N;
unsigned score[8][8][8][8];
bool scored[8][8][8][8];
unsigned get_score(int x1, int y1, int x2, int y2)
{
assert(x1<=x2&&y1<=y2);
if(scored[x1][y1][x2][y2]) return score[x1][y1][x2][y2];
scored[x1][y1][x2][y2]=true;
unsigned sum=0;
for(int x=x1;x<=x2;x++)
for(int y=y1;y<=y2;y++)
sum+=score[x][y][x][y];
score[x1][y1][x2][y2]=sum;
return sum;
}
unsigned dp[8][8][8][8][15];
bool checked[8][8][8][8][15];
unsigned memo(int x1, int y1, int x2, int y2, int n)
{
assert(x1<=x2&&y1<=y2);
if(checked[x1][y1][x2][y2][n])
return dp[x1][y1][x2][y2][n];
checked[x1][y1][x2][y2][n]=true;
if(n==1)
{
dp[x1][y1][x2][y2][n]
=get_score(x1,y1,x2,y2)*get_score(x1,y1,x2,y2);
return dp[x1][y1][x2][y2][n];
}
unsigned ans=INT_MAX;
for(int x=x1,m;x<x2;x++)
{
m=memo(x+1,y1,x2,y2,n-1);
if(m<INT_MAX)
ans=min(ans,get_score(x1,y1,x,y2)*get_score(x1,y1,x,y2)
+memo(x+1,y1,x2,y2,n-1));
m=memo(x1,y1,x,y2,n-1);
if(m<INT_MAX)
ans=min(ans,memo(x1,y1,x,y2,n-1)
+get_score(x+1,y1,x2,y2)*get_score(x+1,y1,x2,y2));
}
for(int y=y1,m;y<y2;y++)
{
m=memo(x1,y+1,x2,y2,n-1);
if(m<UINT_MAX)
ans=min(ans,get_score(x1,y1,x2,y)*get_score(x1,y1,x2,y)
+memo(x1,y+1,x2,y2,n-1));
m=memo(x1,y1,x2,y,n-1);
if(m<UINT_MAX)
ans=min(ans,memo(x1,y1,x2,y,n-1)
+get_score(x1,y+1,x2,y2)*get_score(x1,y+1,x2,y2));
}
dp[x1][y1][x2][y2][n]=ans;
return ans;
}
int main()
{
fin >> N;
for(int y=0;y<=7;y++)
for(int x=0;x<=7;x++)
{
fin >> score[x][y][x][y];
scored[x][y][x][y]=true;
}
double x_=double(get_score(0,0,7,7))/N;
fout << fixed << setprecision(3)
<< sqrt(double(memo(0,0,7,7,N))/N-x_*x_) << endl;
return 0;
}
可能你对下面的文章也感兴趣：
最近评论