poj 1191 dp (기억 화 검색)

제목: 중국어 문제.8 * 8 의 64 칸 을 정 하고 칸 마다 숫자 가 있 습 니 다.이 정사각형 을 n 개의 장방형 으로 잘라 서 각 장방형 에서 숫자의 합 을 최소 화해 야 한다.
사고방식: dp, 기억 화 검색.분산 공식 을 각 제곱 의 평균 수 에서 평균 수의 제곱 을 뺀 형식 으로 쓰 는 것 에 주의해 라.뒤의 하 나 는 상수 이기 때문에 앞의 하 나 를 최소 화하 면 된다.dp (a, b, c, d, m) 는 왼쪽 상단 을 (a, b), 오른쪽 하단 을 (c, d) 로 구 성 된 장방형 을 m 블록 으로 나 누 는 가장 좋 은 값 을 나타 낸다.
또한 왼쪽 상단 점 과 오른쪽 하단 점 을 지정 하여 사각형 의 숫자 합 을 빠르게 구 할 수 있 습 니 다. 코드 에 있 는 s 배열 은 그 점 에서 (1, 1) 사각형 의 숫자 합 을 저장 합 니 다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#define clr(s,t) memset(s,t,sizeof(s))
using namespace std;
#define INF 0x3fffffff
#define n 8
int m;
int s[10][10],dp[n+2][n+2][n+2][n+2][18];
int sum2(int a,int b,int c,int d){
    int res = s[c][d]-s[a-1][d]-s[c][b-1]+s[a-1][b-1];
    return res*res;
}
int solve(int a,int b,int c,int d,int m){
    int i,res = INF;
    if(dp[a][b][c][d][m])
        return dp[a][b][c][d][m];
    if(m==1)
        return dp[a][b][c][d][m] = sum2(a, b, c, d);
    if(a==c && (d-b)<m)                         //     
        return dp[a][b][c][d][m] = INF;
    if(b==d && c-a<m)
        return dp[a][b][c][d][m] = INF;
    for(i = a;i<=c-1;i++){                      //    
        res = min(res,solve(a, b, i, d, m-1) + sum2(i+1,b,c,d));
        res = min(res,sum2(a,b,i,d) + solve(i+1, b, c, d, m-1));
    }
    for(i = b;i<=d-1;i++){                      //    
        res = min(res,solve(a, b, c, i, m-1) + sum2(a,i+1,c,d));
        res = min(res,sum2(a,b,c,i) + solve(a, i+1, c, d, m-1));
    }
    return dp[a][b][c][d][m] = res;
}
int main(){
    int i,j,sum = 0;
    double res = 0;
    clr(dp, 0);
    clr(s, 0);
    scanf("%d",&m);
    for(i = 1;i<=n;i++)
        for(j = 1;j<=n;j++){
            scanf("%d",&s[i][j]);
            sum += s[i][j];
            s[i][j] += s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    res = ((double)sum/m);
    printf("%.3lf
",sqrt((double)solve(1,1,n,n,m)/m-res*res));
    return 0;
}