本文主要是介绍棋盘分割 （POJ - 1191，二维区间 DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一.题目链接：
POJ-1191
二.题目大意：
中文题...
三.分析：
卧艹，这尼玛也太暴力了！
大佬讲解1 大佬讲解2
一开始没想明白状态表示，是我太菜.
dp[i][x1][y1][x2][y2] 表示 将区域 (x1, y1, x2, y2) 切 i 次后的子矩形平方和最小值.
搞清状态表示后，状态转移就很好写啦.
详见代码（没错，我就是懒得讲）
四.代码实现：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int M = 10;
const int inf = 0x3f3f3f3f;int sum[M][M];
int dp[M + 5][M][M][M][M];int cost(int x1, int y1, int x2, int y2)
{int s = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];return s * s;
}int main()
{int n;scanf("%d", &n);for(int i = 1; i <= 8; ++i){for(int j = 1; j <= 8; ++j)scanf("%d", &sum[i][j]);}for(int i = 1; i <= 8; ++i){for(int j = 1; j <= 8; ++j)sum[i][j] += sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1];}memset(dp, inf, sizeof(dp));for(int x1 = 1; x1 <= 8; ++x1){for(int y1 = 1; y1 <= 8; ++y1){for(int x2 = x1; x2 <= 8; ++x2){for(int y2 = y1; y2 <= 8; ++y2){dp[0][x1][y1][x2][y2] = cost(x1, y1, x2, y2);}}}}for(int i = 1; i <= n - 1; ++i){for(int x1 = 1; x1 <= 8; ++x1){for(int y1 = 1; y1 <= 8; ++y1){for(int x2 = x1; x2 <= 8; ++x2){for(int y2 = y1; y2 <= 8; ++y2){for(int x = x1; x < x2; ++x)dp[i][x1][y1][x2][y2]= min(dp[i][x1][y1][x2][y2],min(dp[i - 1][x1][y1][x][y2] + dp[0][x + 1][y1][x2][y2],dp[i - 1][x + 1][y1][x2][y2] + dp[0][x1][y1][x][y2]));for(int y = y1; y < y2; ++y)dp[i][x1][y1][x2][y2]= min(dp[i][x1][y1][x2][y2],min(dp[i - 1][x1][y1][x2][y] + dp[0][x1][y + 1][x2][y2],dp[i - 1][x1][y + 1][x2][y2] + dp[0][x1][y1][x2][y]));}}}}}printf("%.3f\n", sqrt(1.0 * dp[n - 1][1][1][8][8] / n - 1.0 * sum[8][8] * sum[8][8] / n / n));return 0;
}
这篇关于棋盘分割 （POJ - 1191，二维区间 DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
