`
promiser
  • 浏览: 76320 次
  • 性别: Icon_minigender_1
  • 来自: 广州
文章分类
社区版块
存档分类
最新评论

bzoj1048: [HAOI2007]分割矩阵

    博客分类:
  • oi
 
阅读更多

用一个四元组(k,x1,y1,x2,y2)表示以k刀以(x1,y1)为左上角,(x2,y2)为右下角的矩阵的最优值,决策就是把该矩阵划分为两个相邻子矩阵的方法

const int N = 20;
int a, b, n;
DB Sum[N][N], Data[N][N], Dp[N][N][N][N][N], Tot, _x;

inline void Input() {
    scanf("%d%d%d", &a, &b, &n);
    For(i, 1, a)
        For(j, 1, b)
            scanf("%lf", &Data[i][j]), Tot += Data[i][j];
    _x = Tot / n;
    For(i, 1, a)
        For(j, 1, b)
            Sum[i][j] = Sum[i - 1][j] + Sum[i][j - 1] - Sum[i - 1][j - 1] + Data[i][j];
}

inline DB Solve(int Ox1, int Oy1, int Ox2, int Oy2, int T) {
    DB &Cnt = Dp[Ox1][Oy1][Ox2][Oy2][T];
    if(Cnt < INF) return Cnt;
    if(!T) {
        Cnt = (Sum[Ox2][Oy2] + Sum[Ox1 - 1][Oy1 - 1] - Sum[Ox1 - 1][Oy2] - Sum[Ox2][Oy1 - 1]) - _x;
        return Cnt = sqr(Cnt);
    }
    For(i, Ox1, Ox2 - 1)
        Rep(j, T)
            Cnt = min(Cnt, Solve(Ox1, Oy1, i, Oy2, j) + Solve(i + 1, Oy1, Ox2, Oy2, T - j - 1));
    For(i, Oy1, Oy2 - 1)
        Rep(j, T)
            Cnt = min(Cnt, Solve(Ox1, Oy1, Ox2, i, j) + Solve(Ox1, i + 1, Ox2, Oy2, T - j - 1));
    return Cnt;
}
inline void Solve() {
    For(i, 0, a)
    	For(j, 0, b)
    		For(k, 0, a)
    			For(l, 0, b)
    				For(T, 0, n) Dp[i][j][k][l][T] = (DB)MLL;
    Solve(1, 1, a, b, n - 1);
    printf("%.2lf\n", sqrt(Dp[1][1][a][b][n - 1] / n));
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1048");
	#endif
	Input();
	Solve();
	return 0;
}

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics