1 条题解
-
0求乖的小野猫 LV 6 @ 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%
- 上传者