POJ 1191 棋盘分割（区间DP）题解

时间：2022-03-15 14:08:42

题意：中文题面

思路：不知道直接暴力枚举所有情况行不行。。。

我们可以把答案转化为

POJ 1191 棋盘分割（区间DP）题解

所以答案就是求xi2的最小值，那么我们可以直接用区间DP来写。设dp[x1][y1][x2][y2][k]为x1 y1 到 x2 y2 区间分割为k份的最下平方和，显然k = 1是就是区间和的平方。

写了6层for，写出来自己都不信。。。

交C++才过。。。

代码：

#include<cmath>

#include<stack>

#include<cstdio>

#include<vector>

#include<cstring>

#include <iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int maxn =  + ;

const int INF = 0x3f3f3f3f;

const int MOD = ;

int n;

double w[maxn][maxn], dp[maxn][maxn][maxn][maxn][maxn], sum[maxn][maxn];

double get(int x1, int y1, int x2, int y2){

    return sum[x2][y2] - sum[x2][y1 - ] - sum[x1 - ][y2] + sum[x1 - ][y1 - ];

}

int main(){

    scanf("%d", &n);

    memset(sum, , sizeof(sum));

    for(int i = ; i <= ; i++){

        for(int j = ; j <= ; j++){

            scanf("%lf", &w[i][j]);

            sum[i][j] = sum[i - ][j] + sum[i][j - ] - sum[i - ][j - ] + w[i][j];

        }

    }

    double per = sum[][] / n;

    for(int x1 = ; x1 <= ; x1++){

        for(int y1 = ; y1 <= ; y1++){

            for(int x2 = x1; x2 <= ; x2++){

                for(int y2 = y1; y2 <= ; y2++){

                    double ret = get(x1, y1, x2, y2);

                    dp[x1][y1][x2][y2][] = ret * ret;

                }

            }

        }

    }

    for(int k = ; k <= n; k++){

        for(int x1 = ; x1 <= ; x1++){

            for(int y1 = ; y1 <= ; y1++){

                for(int x2 = x1; x2 <= ; x2++){

                    for(int y2 = y1; y2 <= ; y2++){

                        dp[x1][y1][x2][y2][k] = INF;

                        for(int t = x1; t < x2; t++){

                            dp[x1][y1][x2][y2][k] = min(dp[x1][y1][x2][y2][k], dp[x1][y1][t][y2][] + dp[t + ][y1][x2][y2][k - ]);

                            dp[x1][y1][x2][y2][k] = min(dp[x1][y1][x2][y2][k], dp[x1][y1][t][y2][k - ] + dp[t + ][y1][x2][y2][]);

                        }

                        for(int t = y1; t < y2; t++){

                            dp[x1][y1][x2][y2][k] = min(dp[x1][y1][x2][y2][k], dp[x1][y1][x2][t][] + dp[x1][t + ][x2][y2][k - ]);

                            dp[x1][y1][x2][y2][k] = min(dp[x1][y1][x2][y2][k], dp[x1][y1][x2][t][k - ] + dp[x1][t + ][x2][y2][]);

                        }

                    }

                }

            }

        }

    }

    printf("%.3lf\n", sqrt(dp[][][][][n] / n - per * per));

    return ;

}

相关文章