题解

1 条题解

  • 0
    @ 2020-10-16 21:41:57
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    typedef double db;
    inline int read()
    {
        int x=0,f=1; char ch=getchar();
        while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
        return x*f;
    }
    const int N=11,INF=1e9;
    int n,m,K,sum[N][N];
    db f[N][N][N][N][N],P;
    bool vis[N][N][N][N][N];
    inline db calc(int xa,int ya,int xb,int yb) { return sum[xb][yb]-sum[xa-1][yb]-sum[xb][ya-1]+sum[xa-1][ya-1]; }
    db dfs(int xa,int ya,int xb,int yb,int k)
    {
        if(xb-xa+yb-ya<k) return INF;
        db &T=f[xa][ya][xb][yb][k];
        if(vis[xa][ya][xb][yb][k]) return T;
        vis[xa][ya][xb][yb][k]=1; T=INF;
        if(!k) { T=(calc(xa,ya,xb,yb)-P)*(calc(xa,ya,xb,yb)-P); return T; }
        for(int i=0;i<k;i++)
            for(int j=xa;j<xb;j++)
                T=min(T, dfs(xa,ya,j,yb,i)+dfs(j+1,ya,xb,yb,k-i-1) );
        for(int i=0;i<k;i++)
            for(int j=ya;j<yb;j++)
                T=min(T, dfs(xa,ya,xb,j,i)+dfs(xa,j+1,xb,yb,k-i-1) );
        return T;
    }
    int main()
    {
        n=read(),m=read(),K=read();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++) sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+read();
        P=1.0*sum[n][m]/K;
        printf("%.2lf\n",sqrt( dfs(1,1,n,m,K-1)/K ));
        return 0;
    }
    
  • 1

信息

难度
9
分类
(无)
标签
递交数
3
已通过
2
通过率
67%
上传者