动态规划

也是经典题目，黑书上也有介绍。今晚上JAVA在想，想了一下想出来，需要五维，大矩形的值由小矩形得到，这个状态转移方程个人感觉还是比较想到，但是一些细节的地方还没想到怎么处理，回来瞄一眼黑书得到了标准差的一个转化公式，所以疑团解开，便开始打代码（看黑书过程中它写的状态转移方程和我想的一样，但是有一些细微的细节，我感觉我这样处理比较保险，我后来细想了一下它的，虽然没有判断但是可能也不会出错，但是更倾向于我自己想的那种，就是关于横着切和竖着切的范围）

 

忘记搞掉注释WA了一次，搞掉后就AC了，算是 一次成型不用debug，后来上网找报告，大家几乎都是用double来开数组的，其实不用double来开也可以的我的代码中就是简单地用int（或许double真的保险一点避免精度问题）

分析在代码注释中

/*题目固定是8*8，本来想用点的坐标来表示矩形的，但是发现用标号来表示会方便一点对于最小的小方格，用(i,j)表示，即第i行第j列的小方格，注意不是点的坐标所以对于一个矩形，我们用它左上角的小方格和右下角的小方格来表示例如，整个棋盘就是(1,1),(8,8)另外题目要求，每次分割出一个矩形后，剩下的也必须是矩形那么其实每次分割只能切一刀，如果是切两刀得到的矩形，那么剩下的就不会是矩形了只能横着切或者竖着切，而且一切的话要从头切到底（这很容易理解）另外还有一个东西之前理解错了，就是一刀切下去会得到两个矩形，选一个为本次切割得到的，以后只能切另一个，选出来的那个以后不能再切了（如果是两者都能切，感觉复杂很多）然后动态转移方程觉得还是比较容易想到的，大矩形dp值由小矩形dp值推得来还要加上次数，dp[n][x1][y1][x2][y2]就是要令当前矩形分出n个小矩形，也就是切割n-1刀我们要的目标值就是dp[n][1][1][8][8]一：横着切，当前矩形将会分成上下两份1.选上面：dp[k][x1][y1][x2][y2]=s[x1][y1][x][y2]+dp[k-1][x+1][y1][x2][y2];2.选下面：dp[k][x1][y1][x2][y2]=s[x+1][y1][x2][y2]+dp[k-1][x1][y1][x][y2];x1<=x
     
      <=y
      
       #include 
       
        #include 
        
         #define min(a,b) a
         
          x1)  //至少有两行才能横着切    {        //1.选上面：dp[k][x1][y1][x2][y2]=s[x1][y1][x][y2]+dp[k-1][x+1][y1][x2][y2];        //2.选下面：dp[k][x1][y1][x2][y2]=s[x+1][y1][x2][y2]+dp[k-1][x1][y1][x][y2];        for(x=x1; x
          
           y1) //至少有两列才能竖着切 { //1.选左边：dp[k][x1][y1][x2][y2]=s[x1][y1][x2][y]+dp[k-1][x1][y+1][x2][y2]; //2.选右边：dp[k][x1][y1][x2][y2]=s[x1][y+1][x2][y2]+dp[k-1][x1][y1][x2][y]; for(y=y1; y