过不了样例求条
查看原帖
过不了样例求条
1501877
wuzebang2009楼主2025/1/29 20:14
#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]));
}
2025/1/29 20:14
加载中...