现在的位置: 首页 > 算法 > 正文

poj1191棋盘分割—典型动态规划

2019年04月18日 算法 ⁄ 共 2208字 ⁄ 字号 评论关闭

  check out后,这几天刚好闷骚期,随便玩了一道,典型的动态规划。一开始wrong answer,后来发现sumit时候忘记把测试时候ifstream 改回来,还有根据讨论,要用long double,改了一下就ok了。

  开始DP前先推导下均方差公式,发现均方差就等于sqrt( sum(Xi^2)/n - (sum/n)^2 ),因为sum和n 已知,所以问题变成了求sum(Xi^2)/n的最小值,即每个矩形块的值的平方和的总和。

   subChessSquare[i][j][h][w][n] 表示 以(i,j)为起点,w为宽,h为高的矩形块 切n次的 sum(Xi^2)的 最小值 。DP子问题是对这个矩形块切一刀,求对其中一个剩下的矩形块切n-1次的最优值。 

#include <iomanip>
using namespace std;

int main()
{

long double chess[8][8];

long double ValueSum=0.0f;

long double subChessSquare[8][8][8][8][15];

int nNumber;

const long double MAXNUMBER=(long double)(1<<30);

cin>>nNumber;

for(int i=0;i<8;i++)

for(int j=0;j<8;j++)

{

cin>>chess[i][j];

ValueSum+=chess[i][j];

}

//

for(int h=1;h<=8;h++)

for(int w=1;w<=8;w++)

for(int i=0;i<=8-h;i++)

for(int j=0;j<=8-w;j++)

{

subChessSquare[i][j][h][w][0]=0;

for(int subi=i;subi<i+h;subi++)

for(int subj=j;subj<j+w;subj++)

{

subChessSquare[i][j][h][w][0]+=chess[subi][subj];

}

subChessSquare[i][j][h][w][0]=pow(subChessSquare[i][j][h][w][0],2);

}

for(int n=1;n<=nNumber;n++)

{

for(int h=1;h<=8;h++)

for(int w=1;w<=8;w++)

for(int i=0;i<=8-h;i++)

for(int j=0;j<=8-w;j++)

{

subChessSquare[i][j][h][w][n]=MAXNUMBER;

if(h==1 && w==1)

{

  subChessSquare[i][j][h][w][n]=subChessSquare[i][j][h][w][0];

  continue;

}

//Cut vertically

for(int nw=1;nw<w;nw++)

{

//choose right to go on cutting

  long double tmpValue=subChessSquare[i][j][h][nw][0]+subChessSquare[i][j+nw][h][w-nw][n-1];

  if(tmpValue<subChessSquare[i][j][h][w][n])

  {

    subChessSquare[i][j][h][w][n]=tmpValue;

  }


//choose left to go on cutting

tmpValue=subChessSquare[i][j][h][nw][n-1]+subChessSquare[i][j+nw][h][w-nw][0];

if(tmpValue<subChessSquare[i][j][h][w][n])

{

  subChessSquare[i][j][h][w][n]=tmpValue;

}

}

//Cut horizontally

for(int nh=1;nh<h;nh++)

{

//Choose down to go on cutting.

long double tmpValue=subChessSquare[i][j][nh][w][0]+subChessSquare[i+nh][j][h-nh][w][n-1];

if(tmpValue<subChessSquare[i][j][h][w][n])

{

subChessSquare[i][j][h][w][n]=tmpValue;

}

//Choose top to go on cutting.

tmpValue=subChessSquare[i][j][nh][w][n-1]+subChessSquare[i+nh][j][h-nh][w][0];

if(tmpValue<subChessSquare[i][j][h][w][n])

{

  subChessSquare[i][j][h][w][n]=tmpValue;

}

}

}

}

long double msDeviation=sqrt( subChessSquare[0][0][8][8][nNumber-1]/nNumber - pow((long double)ValueSum/nNumber,2) );

//std::cout<<setiosflags(ios::fixed)<<setprecision(3)<<msDeviation<<endl;

printf("%.3f",msDeviation );

}

抱歉!评论已关闭.