題目鏈接http://poj.org/problem?id=1191

Problem:?1191Memory:?568KTime:?16MSLanguage:?C++Result:?Accepted

解題報告：

1、公式可以利用數(shù)學(xué)方法化簡，就是求各個矩陣上的數(shù)（的和）的平方和最小。

2、每一次分割都有四種情況（遞歸）。

3、每一次分割的位置要進(jìn)行比較，從而找到最佳。

#include <stdio.h> #include <math.h> #include <algorithm> #include <string.h>using namespace std;int s[9][9];//每個格子的分?jǐn)?shù) int sum[9][9];//(1,1)到(i,j)的矩形分?jǐn)?shù)的和 int res[15][9][9][9][9];//fun的記錄表int calsum(int x1,int y1,int x2,int y2)//(x1,y1)到(x2,y2)的矩形分?jǐn)?shù)和 {return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]; }int fun(int n,int x1,int y1,int x2,int y2)//以(x1,y1)為左上角，(x2,y2)為右下角的矩形的棋盤分割成n分后的最小平方和 {int t,a,b,c,e;int MIN=0x3f3f3f3f;if(res[n][x1][y1][x2][y2]!=-1)return res[n][x1][y1][x2][y2];if(n==1){t=calsum(x1,y1,x2,y2);res[n][x1][y1][x2][y2]=t*t;return t*t;}for(a=x1;a<x2;a++){c=calsum(a+1,y1,x2,y2);//右邊的矩陣的和e=calsum(x1,y1,a,y2);//左邊的矩陣的和t=min(fun(n-1,x1,y1,a,y2)+c*c,fun(n-1,a+1,y1,x2,y2)+e*e);if(MIN>t) MIN=t;}for(b=y1;b<y2;b++){c=calsum(x1,b+1,x2,y2);//下面的矩陣的和e=calsum(x1,y1,x2,b);//上面的矩陣的和t=min(fun(n-1,x1,y1,x2,b)+c*c,fun(n-1,x1,b+1,x2,y2)+e*e);if(MIN>t) MIN=t;}res[n][x1][y1][x2][y2]=MIN;return MIN; }int main() {memset(sum,0,sizeof(sum));memset(res,-1,sizeof(res));int n;scanf("%d",&n);for(int i=1;i<9;i++){for(int j=1,rowsum=0;j<9;j++){scanf("%d",&s[i][j]);rowsum=rowsum+s[i][j];sum[i][j]=sum[i-1][j]+rowsum;}}double result=n*fun(n,1,1,8,8)-sum[8][8]*sum[8][8];printf("%.3f\n",sqrt(result/(n*n)));return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/TreeDream/p/5203214.html

總結(jié)

以上是生活随笔為你收集整理的递归，记忆化搜索，（棋盘分割）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。