POJ 1191 记忆化搜索

（我是不会告诉你我是抄的http://www.cnblogs.com/scau20110726/archive/2013/02/27/2936050.html这个人的）

一开始没有想到要化一下方差的式子怎么搞都挂……

尴尬

/*
题目固定是8*8，本来想用点的坐标来表示矩形的，但是发现用标号来表示会方便一点
对于最小的小方格，用(i,j)表示，即第i行第j列的小方格，注意不是点的坐标
所以对于一个矩形，我们用它左上角的小方格和右下角的小方格来表示
例如，整个棋盘就是(1,1),(8,8)
另外题目要求，每次分割出一个矩形后，剩下的也必须是矩形
那么其实每次分割只能切一刀，如果是切两刀得到的矩形，那么剩下的就不会是矩形了
只能横着切或者竖着切，而且一切的话要从头切到底（这很容易理解）
另外还有一个东西之前理解错了，就是一刀切下去会得到两个矩形，
选一个为本次切割得到的，以后只能切另一个，选出来的那个以后不能再切了
（如果是两者都能切，感觉复杂很多）
然后动态转移方程觉得还是比较容易想到的，大矩形dp值由小矩形dp值推得来
还要加上次数，dp[n][x1][y1][x2][y2]就是要令当前矩形分出n个小矩形，也就是切割n-1刀
我们要的目标值就是dp[n][1][1][8][8]
一：横着切，当前矩形将会分成上下两份
1.选上面：dp[k][x1][y1][x2][y2]=s[x1][y1][x][y2]+dp[k-1][x+1][y1][x2][y2];
2.选下面：dp[k][x1][y1][x2][y2]=s[x+1][y1][x2][y2]+dp[k-1][x1][y1][x][y2];
x1<=x<x2
二：竖着切，当前矩形将会分成左右两份
1.选左边：dp[k][x1][y1][x2][y2]=s[x1][y1][x2][y]+dp[k-1][x1][y+1][x2][y2];
2.选右边：dp[k][x1][y1][x2][y2]=s[x1][y+1][x2][y2]+dp[k-1][x1][y1][x2][y];
y1<=y<y2
当k=1时也就是不用再继续分割了，dp[1][x1][y1][x2][y2]=s[x1][y1][x2][y2];
显然这个DP用记忆化搜索来做更合适，递推的话感觉很难写
最后强调一个细节问题，dp数组全部初始化为-1，表示还没被计算，
然后  dp[1][x1][y1][x2][y2]=s[x1][y1][x2][y2]  这个也好理解，就是不用切的时候的dp值
最后，比如当前要求的是dp[k][x1][y1][x2][y2]，一开始要赋初值为INF，再开始枚举切割方案
因为对于dp[k][x1][y1][x2][y2]，要分出k块矩形，但是不一定能分得到，可能根本不够分
所以当前状态如果根本分不出k个小矩形的话，这个状态是一个不可能的状态，为INF
整个枚举过程中它的值也不会更新
*/

这个题解中有两个多余的判断可以去掉。。

//By SiriusRen
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,a[9][9],f[9][9][9][9][65],s[9][9][9][9],sum;
int dfs(int x1,int y1,int x2,int y2,int k){
    if(~f[x1][y1][x2][y2][k])return f[x1][y1][x2][y2][k];
    int temp=0x3fffffff;
    for(int i=x1+1;i<=x2;i++){
        temp=min(temp,dfs(i,y1,x2,y2,k-1)+s[x1][y1][i-1][y2]);
        temp=min(temp,dfs(x1,y1,i-1,y2,k-1)+s[i][y1][x2][y2]);
    }
    for(int i=y1+1;i<=y2;i++){
        temp=min(temp,dfs(x1,i,x2,y2,k-1)+s[x1][y1][x2][i-1]);
        temp=min(temp,dfs(x1,y1,x2,i-1,k-1)+s[x1][i][x2][y2]);
    }
    return f[x1][y1][x2][y2][k]=temp;
}
int main(){
    memset(f,-1,sizeof(f));
    scanf("%d",&n);
    for(int i=1;i<=8;i++)
        for(int j=1;j<=8;j++)
            scanf("%d",&a[i][j]),sum+=a[i][j];
    for(int x1=1;x1<=8;x1++)
        for(int y1=1;y1<=8;y1++)
            for(int x2=x1;x2<=8;x2++)
                for(int y2=y1;y2<=8;y2++){
                    int temp=0;
                    for(int i=x1;i<=x2;i++)
                        for(int j=y1;j<=y2;j++)
                            temp+=a[i][j];
                    f[x1][y1][x2][y2][1]=s[x1][y1][x2][y2]=temp*temp;
                }
    double tmp=1.0*sum/n;
    printf("%.3lf
",sqrt(1.0*dfs(1,1,8,8,n)/n-tmp*tmp));
}

POJ 1191 记忆化搜索

相关推荐