poj1191--棋盘分割(dp)

本文主要是介绍poj1191--棋盘分割(dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

将一个８*８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)

原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。
x _i为第i块矩形棋盘的总分。
请编程对给出的棋盘及n，求出O'的最小值。

Input

Output

Sample Input

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

Sample Output

1.633

求方差最小

(x1,y1)代表一个方块的左上角，（x2,y2）方块的右下角。

dp[i][j] i表示当前分割为i块是，并且，最后一块为j，j = x1 * 1000 + y1 * 100 + x2 * 10 + y2,将一个方块的坐标压到一个数中，让dp[i][j]最小，最终得到dp[n][j]找出最小值

对于每一个方块枚举可以切开的位置，和之后得到的方块，。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std ;
#define LL __int64
#define INF 0x3f3f3f3f
int Map[10][10] ;
double dp[20][11000] ;
double f(int x1,int y1,int x2,int y2,double x)
{
double ans ;
ans = Map[x2][y2] - Map[x2][y1] - Map[x1][y2] + Map[x1][y1] ;
ans = ( ans - x ) * ( ans - x ) ;
return ans ;
}
int main()
{
int i , j , k , l , n , x1 , y1 , x2 , y2 ;
double x = 0 , ans = INF , temp , temp1 , temp2 ;
scanf("%d", &n) ;
memset(Map,0,sizeof(Map)) ;
for(i = 1 ; i <= 8 ; i++)
{
for(j = 1 ; j <= 8 ; j++)
{
scanf("%d", &Map[i][j]) ;
Map[i][j] += Map[i][j-1] ;
}
for(j = 1 ; j <= 8 ; j++)
Map[i][j] += Map[i-1][j] ;
}
/*for(i = 0 ; i <= 8 ; i++)
{
for(j = 0 ; j <= 8 ; j++)
printf("%d ", Map[i][j]) ;
printf("\n") ;
}*/
x = Map[8][8]*1.0/n ;
//printf("%lf\n", x) ;
for(i = 0 ; i <= n ; i++)
for(j = 0 ; j <= 8888 ; j++)
dp[i][j] = INF ;
dp[1][88] = (Map[8][8]*1.0 - x) * (Map[8][8]*1.0 - x) ;
for(i = 1 ; i < n ; i++)
{
for(j = 0 ; j <= 8888 ; j++)
{
x1 = j/1000%10 ;
y1 = j/100%10 ;
x2 = j/10%10 ;
y2 = j%10 ;
temp = f(x1,y1,x2,y2,x) ;
for(k = x1+1 ; k < x2 ; k++)
{
temp1 = f(x1,y1,k,y2,x) ;
temp2 = f(k,y1,x2,y2,x) ;
l = x1*1000+y1*100+k*10+y2 ;
if( dp[i+1][l] > dp[i][j] - temp + temp1 + temp2 )
dp[i+1][l] = dp[i][j] - temp + temp1 + temp2 ;
l = k*1000+y1*100+x2*10+y2 ;
if( dp[i+1][l] > dp[i][j] - temp + temp1 + temp2 )
dp[i+1][l] = dp[i][j] - temp + temp1 + temp2 ;
}
for(k = y1+1 ; k < y2 ; k++)
{
temp1 = f(x1,y1,x2,k,x) ;
temp2 = f(x1,k,x2,y2,x) ;
l = x1*1000+y1*100+x2*10+k ;
if( dp[i+1][l] > dp[i][j] - temp + temp1 + temp2 )
dp[i+1][l] = dp[i][j] - temp + temp1 + temp2 ;
l = x1*1000+k*100+x2*10+y2 ;
if( dp[i+1][l] > dp[i][j] - temp + temp1 + temp2 )
dp[i+1][l] = dp[i][j] - temp + temp1 + temp2 ;
}
}
}
for(j = 0 ; j <= 8888 ; j++)
ans = min(ans,dp[n][j]) ;
printf("%.3lf\n", sqrt(ans/(n*1.0))) ;
return 0;
}

这篇关于poj1191--棋盘分割(dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！