題解 P1436 【棋盤分割】

題目連結

其實呢大緻思路和下面的大佬們都很像。

發這篇題解的目的就是加了一點~~優化~~騙分技巧。

轉移方程：

設$dp[i][j][x][y][k]$表示左上$(i,j)$，右下$(x,y)$，第$k$次割的最大面積。

則對于

 $\sum_{k=1}^{n}$

開始更新，有：(~~一口氣讀完這個方程~~)

 $\sum_{i=1}^{8} \sum_{j=1}^{8} \sum_{x=1}^{8} \sum_{y=1}^{8}$       

$a=j……y-1;b=i……x-1;$

 $dp[i][j][x][y][k]=$

 $min($

 $min(dp[i][j][x][a][k-1]+dp[i][a+1][x][y][0],dp[i][j][x][a][0]+dp[i][a+1][x][y][k-1]),$

 $min(dp[i][j][b][y][k-1]+dp[b+1][j][x][y][0],dp[i][j][b][y][0]+dp[b+1][j][x][y][k-1])$

 $);$

但是。

 别以為推出了方程就萬事大吉了！！！

您的邊界條件呢（這題~~很簡單~~）。

但是這題的初始化是重點！！！重點！！！重點！！！

好幾篇都是6重循環暴力算的。

本寶寶：字首和先求出來就好了。

那麼好，初始化的話是要把所有左上為$(i,j)$右上為$(x,y)$,割了0次的面積求出來。這裡，本寶寶用了一個字首和的思想和容斥原理。

先在輸入的時候就處理出來所有左上$(1,1)$右上$(i,j)$的得分（字首和）；

然後利用容斥原理（具體見代碼）

能少些~~三~~兩個循環呢。。。

上代碼（碼風不好請原諒）

//by Su Qingnian
//QAQ
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;//n是總共切的刀數
int map[9][9];//存圖，價值
int sum[9][9];//字首和數組
int dp[9][9][9][9][15];//dp暴力數組
inline void add(int i,int j)
{
//這個函數是計算字首和數組。左上(1,1)右下(i,j)的價值
//好好想想為什麼。（擴充這個點時左邊矩形+右邊矩形-重疊的部分+這個點的價值）
    sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+map[i][j];
    return ;
}
inline int s(int x1,int y1,int x2,int y2)
{
//這個是用來計算左上(x1,y1)右下(x2,y2)的價值
//還是容斥原理
    int now=sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
    return now;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=8;i++)
      for(int j=1;j<=8;j++)
      scanf("%d",&map[i][j]),
      add(i,j);//輸入，處理字首和
    
//debug
//    for(int i=1;i<=8;i++,puts(""))
//      for(int j=1;j<=8;j++)
//      printf("%-5d ",sum[i][j]);
//處理切0刀時各矩形價值的平方
    for(int i=1;i<=8;i++)
     for(int j=1;j<=8;j++)
       for(int x=i;x<=8;x++)
         for(int y=j;y<=8;y++)
           dp[i][j][x][y][0]+=s(i,j,x,y),
           dp[i][j][x][y][0]*=dp[i][j][x][y][0];
//dp過程，深吸一口氣讀完這一面方程。
    for(int k=1;k<n;k++)
      for(int i=1;i<=8;i++)
        for(int j=1;j<=8;j++)
          for(int x=i;x<=8;x++)
            for(int y=j;y<=8;y++)
            {
                int minn=0x3f3f3f3f;
                for(int a=j;a<y;a++)
                  minn=min(minn,min(dp[i][j][x][a][k-1]+dp[i][a+1][x][y][0],dp[i][j][x][a][0]+dp[i][a+1][x][y][k-1]));
                for(int b=i;b<x;b++)
                  minn=min(minn,min(dp[i][j][b][y][k-1]+dp[b+1][j][x][y][0],dp[i][j][b][y][0]+dp[b+1][j][x][y][k-1]));
                dp[i][j][x][y][k]=minn;
            }
    printf("%d",dp[1][1][8][8][n-1]);
 //輸出，程式拜拜。
    return 0;
}