题意：中文省略.
思路：黑说p116有讲解，
主要的状态转移方程为
横着切：
dp[k][x1][y1][x2][y2] = min(dp[k - 1][x1][y1][mid][y2] + dp[1][mid][y1][x2][y2],dp[k - 1][mid][y1][x2][y2] + dp[1][x1][y1][mid][y2]); x1 + 1 <= mid < x2
竖着切：
dp[k][x1][y1][x2][y2] = min(dp[k - 1][x1][y1][x2][mid] + dp[1][x1][mid][x2][y2],dp[k - 1][x1][mid][x2][y2] + dp[1][x1][y1][x2][mid]); y1 + 1<= mid < y2
View Code #include <iostream> #include <cmath> #include <cstdio> #include <cstring> #define maxn 17 #define N 8 using namespace std; const int inf = 99999999; int dp[maxn][ 9][ 9][ 9][ 9]; int map[ 9][ 9]; int getDP( int k, int x1, int y1, int x2, int y2) { int mid; int ans = inf; for (mid = x1 + 1; mid < x2; ++mid) { ans = min(ans,dp[k - 1][x1][y1][mid][y2] + dp[ 1][mid][y1][x2][y2]); ans = min(ans,dp[k - 1][mid][y1][x2][y2] + dp[ 1][x1][y1][mid][y2]); } for (mid = y1 + 1; mid < y2; ++mid) { ans = min(ans,dp[k - 1][x1][y1][x2][mid] + dp[ 1][x1][mid][x2][y2]); ans = min(ans,dp[k - 1][x1][mid][x2][y2] + dp[ 1][x1][y1][x2][mid]); } return ans; } int main() { // freopen("d.txt","r",stdin); int n,i,j,k; int x1,y1,x2,y2; scanf( " %d ",&n); memset(map, 0, sizeof(map)); int sum = 0; // map存每个矩形的和 for (i = 1; i <= N; ++i) for (j = 1; j <= N; ++j) { scanf( " %d ",&map[i][j]); sum += map[i][j]; map[i][j] += map[i][j - 1] + map[i - 1][j] - map[i - 1][j - 1]; } // 出事话dp将所有划分成一个的求出来 memset(dp, 0, sizeof(dp)); for (x1 = 0; x1 < N; ++x1) for (y1 = 0; y1 < N; ++y1) for (x2 = x1 + 1; x2 <= N; ++x2) for (y2 = y1 + 1; y2 <= N; ++y2) { int tmp = map[x2][y2] - map[x1][y2] - map[x2][y1] + map[x1][y1]; dp[ 1][x1][y1][x2][y2] = tmp*tmp; } // 枚举求解 for (k = 2; k <= n; ++k) for (x1 = 0; x1 < N; ++x1) for (y1 = 0; y1 < N; ++y1) for (x2 = x1 + 1; x2 <= N; ++x2) for (y2 = y1 + 1; y2 <= N; ++y2) { dp[k][x1][y1][x2][y2] = getDP(k,x1,y1,x2,y2); } double ans = ( 1.0*dp[n][ 0][ 0][ 8][ 8])/n - ( 1.0*sum*sum)/(n*n* 1.0); printf( " %.3lf\n ",sqrt(ans)); return 0;
记忆化搜索：
这里只要能够推出状态转移方程，其实记忆化搜索就很好写了。
View Code #include <iostream> #include <cmath> #include <cstdio> #include <cstring> #define maxn 17 #define N 8 using namespace std; const int inf = 99999999; int dp[maxn][ 9][ 9][ 9][ 9]; int map[ 9][ 9]; /* int getDP(int k,int x1,int y1,int x2,int y2){ int mid; int ans = inf; for (mid = x1 + 1; mid < x2; ++mid) { ans = min(ans,dp[k - 1][x1][y1][mid][y2] + dp[1][mid][y1][x2][y2]); ans = min(ans,dp[k - 1][mid][y1][x2][y2] + dp[1][x1][y1][mid][y2]); } for (mid = y1 + 1; mid < y2; ++mid) { ans = min(ans,dp[k - 1][x1][y1][x2][mid] + dp[1][x1][mid][x2][y2]); ans = min(ans,dp[k - 1][x1][mid][x2][y2] + dp[1][x1][y1][x2][mid]); } return ans;} */ int getS( int x1, int y1, int x2, int y2) { return map[x2][y2] - map[x1][y2] - map[x2][y1] + map[x1][y1]; } int DP( int k, int x1, int y1, int x2, int y2) { int mid; if (dp[k][x1][y1][x2][y2] != 0) return dp[k][x1][y1][x2][y2]; // 记忆的由来 if (k == 1) // 分割到最小取得值 { int tp = getS(x1,y1,x2,y2); dp[ 1][x1][y1][x2][y2] = tp*tp; return tp*tp; } int ans = inf; // 横向切割 for (mid = x1 + 1; mid < x2; ++mid) { ans = min(ans,DP(k - 1,x1,y1,mid,y2) + DP( 1,mid,y1,x2,y2)); ans = min(ans,DP(k - 1,mid,y1,x2,y2) + DP( 1,x1,y1,mid,y2)); } // 纵向切割 for (mid = y1 + 1; mid < y2; ++mid) { ans = min(ans,DP(k - 1,x1,y1,x2,mid) + DP( 1,x1,mid,x2,y2)); ans = min(ans,DP(k - 1,x1,mid,x2,y2) + DP( 1,x1,y1,x2,mid)); } dp[k][x1][y1][x2][y2] = ans; return ans; } int main() { // freopen("d.txt","r",stdin); int n,i,j; scanf( " %d ",&n); memset(map, 0, sizeof(map)); int sum = 0; // map存每个矩形的和 for (i = 1; i <= N; ++i) for (j = 1; j <= N; ++j) { scanf( " %d ",&map[i][j]); sum += map[i][j]; map[i][j] += map[i][j - 1] + map[i - 1][j] - map[i - 1][j - 1]; } memset(dp, 0, sizeof(dp)); int tmp = DP(n, 0, 0, 8, 8); double ans = ( 1.0*tmp)/n - (sum*sum* 1.0)/(n*n* 1.0); printf( " %.3lf\n ",sqrt(ans)); return 0;