poj1191 把一个矩形分成n块,求其均方差最小 dp

xiaoxiao2021-02-27  446

#include<cstdio> #include<cstring> #include<cmath> #define MIN(x,y) ((x)>(y)?(y):(x)) #define INF 0x3f3f3f3f using namespace std; int N; int map[10][10]; int dp[16][10][10][10][10]; int cal(int x1,int x2,int y1,int y2) { int ans=map[x2][y2]-map[x2][y1-1]-map[x1-1][y2]+map[x1-1][y1-1]; return ans*ans; } int dfs(int x1,int x2,int y1,int y2,int n) { if(dp[n][x1][x2][y1][y2]!=-1) return dp[n][x1][x2][y1][y2]; if(n==N-1) return dp[n][x1][x2][y1][y2]=cal(x1,x2,y1,y2); int t=INF; for(int k=x1;k<x2;k++) { t=MIN(t,dfs(x1,k,y1,y2,n+1)+cal(k+1,x2,y1,y2)); t=MIN(t,dfs(k+1,x2,y1,y2,n+1)+cal(x1,k,y1,y2)); } for(int k=y1;k<y2;k++) { t=MIN(t,dfs(x1,x2,y1,k,n+1)+cal(x1,x2,k+1,y2)); t=MIN(t,dfs(x1,x2,k+1,y2,n+1)+cal(x1,x2,y1,k)); } return dp[n][x1][x2][y1][y2]=t; } int main() { scanf("%d",&N); memset(dp,-1,sizeof(dp)); memset(map,0,sizeof(map)); for(int i=1;i<=8;i++) for(int j=1;j<=8;j++) { scanf("%d",&map[i][j]); map[i][j]+=map[i-1][j]+map[i][j-1]-map[i-1][j-1]; } double average=(double)map[8][8]/N; printf("%.3f\n",sqrt(dfs(1,8,1,8,0)*1.0/N-average*average)); }
转载请注明原文地址: https://www.6miu.com/read-828.html

最新回复(0)