P5752 [NOI1999] 棋盘分割

题目传送门

wrong anwser

#include<bits/stdc++.h>
using namespace std;
const int n=8;
double dp[20][10][10][10][10];
int a[10][10],s[10][10];
int w;
double x;

int main(){
    memset(dp,0x3f,sizeof dp);
    cin>>w; 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
        }
    }
    x=(double)s[8][8]/w;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int q=1;q<=i;q++){
                for(int p=1;p<=j;p++){
                    double t=s[i][j]-s[q-1][j]-s[i][p-1]+s[q-1][p-1]-x;
                    dp[1][i][j][q][p]=t*t/w;
                }
            }
        }
    }
    for(int tk=2;tk<=w;tk++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                for(int q=1;q<=i;q++){
                    for(int p=1;p<=j;p++){
                        for(int t=q+1;t<=i;t++) dp[tk][i][j][q][p]=min(dp[tk][i][j][q][p],min(dp[tk-1][t][j][q][p]+dp[1][i][j][t-1][p],dp[1][t][j][q][p]+dp[tk-1][i][j][t-1][p]));//分割上面还是下面
                        for(int t=p+1;t<=j;t++) dp[tk][i][j][q][p]=min(dp[tk][i][j][q][p],min(dp[tk-1][i][t][q][p]+dp[1][i][j][q][t-1],dp[1][i][t][q][p]+dp[tk-1][i][j][q][t-1]));//分割右边还是左边
                    }
                }
            }
        }
    }
    printf("%.3lf",sqrt(dp[w][n][n][1][1]));
}

AC

#include<bits/stdc++.h>
using namespace std;
const int n=8;
double dp[20][10][10][10][10];
int a[10][10],s[10][10];
int w;
double x;

int main(){
    // memset(dp,0x3f,sizeof dp);
    cin>>w; 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
        }
    }
    x=(double)s[8][8]/w;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int q=i;q<=n;q++){
                for(int p=j;p<=n;p++){
                    double t=s[q][p]-s[i-1][p]-s[q][j-1]+s[i-1][j-1]-x;
                    dp[1][i][j][q][p]=t*t/w;
                }
            }
        }
    }
    for(int tk=2;tk<=w;tk++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                for(int q=i;q<=n;q++){
                    for(int p=j;p<=n;p++){
                        dp[tk][i][j][q][p]=1e9;
                        for(int t=i+1;t<=q;t++) dp[tk][i][j][q][p]=min(dp[tk][i][j][q][p],min(dp[tk-1][t][j][q][p]+dp[1][i][j][t-1][p],dp[1][t][j][q][p]+dp[tk-1][i][j][t-1][p]));//分割上面还是下面
                        for(int t=j+1;t<=p;t++) dp[tk][i][j][q][p]=min(dp[tk][i][j][q][p],min(dp[tk-1][i][t][q][p]+dp[1][i][j][q][t-1],dp[1][i][t][q][p]+dp[tk-1][i][j][q][t-1]));//分割右边还是左边
                    }
                }
            }
        }
    }
    printf("%.3lf",sqrt(dp[w][1][1][n][n]));
}

这就体现出线性DP的特性了——沿着各个维度线性增长，由于大的矩形是由小矩形的方差推出来的，所以顺序应该是从小到大，也就是从 $(i,j)$ 较靠近原点的地方递推更远的点，如果先找到一个$(i,j)$再枚举递推前面的点，这就不符合线性的要求了，大家对DP有什么见解吗？