题解 P1436 【棋盘分割】

· · 题解

其实呢大致思路和下面的大佬们都很像。 发这篇题解的目的就是加了一点优化骗分技巧。

转移方程：

设dp[i][j][x][y][k]表示左上(i,j)，右下(x,y)，第k次割的最大面积。 则对于

\sum_{k=1}^{n}

开始更新，有：(一口气读完这个方程)

∑_{i=1}^{8}∑_{j=1}^{8}∑_{x=1}^{8}∑_{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;
}