递归，记忆化搜索，（棋盘分割）

题目链接http://poj.org/problem?id=1191

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

解题报告：

1、公式可以利用数学方法化简，就是求各个矩阵上的数（的和）的平方和最小。

2、每一次分割都有四种情况（递归）。

3、每一次分割的位置要进行比较，从而找到最佳。

#include <stdio.h> #include <math.h> #include <algorithm> #include <string.h>using namespace std;int s[9][9];//每个格子的分数 int sum[9][9];//(1,1)到(i,j)的矩形分数的和 int res[15][9][9][9][9];//fun的记录表int calsum(int x1,int y1,int x2,int y2)//(x1,y1)到(x2,y2)的矩形分数和 {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; }

 

 

转载于:https://www.cnblogs.com/TreeDream/p/5203214.html

总结

以上是生活随笔为你收集整理的递归，记忆化搜索，（棋盘分割）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。