[动态规划] pku1191 三维DP

评论19次阅读2007.10.08 9:12; 作者：Felicia　

不错的DP题。状态f[i][x1][y1][x2][y2]表示要把(x1,y1) — (x2, y2) 分割成i块所得到的最小平方和（平方和指的是每块矩形的和的平方和）。然后根据水平和竖直切割进行状态转移。这样计算出f[n][1][1][8][8]得到整个棋盘分割成n块得到的最小平方和，然后代入均方差公式算得结果。

下面是我的代码

下载: pku1191.cpp
/**********************************************************************
Author: WHU_GCC
Created Time: 2007-10-1 19:01:11
File Name: pku1191.cpp
Description:
**********************************************************************/
#include <iostream>
#include <cmath>
using namespace std;
 
#define out(x) (cout << #x << ": " << x << endl)
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) { for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
 
int n;
int a[9][9], g[9][9];
int f[16][9][9][9][9];
 
inline int sum(int x1, int y1, int x2, int y2)
{
    return (g[x2][y2] - g[x1 - 1][y2] - g[x2][y1 - 1] + g[x1 - 1][y1 - 1])
        * (g[x2][y2] - g[x1 - 1][y2] - g[x2][y1 - 1] + g[x1 - 1][y1 - 1]);
}
 
int dp(int k, int x1, int y1, int x2, int y2)
{
    if (f[k][x1][y1][x2][y2] != maxint)
        return f[k][x1][y1][x2][y2];
    if (k == 1)
        return f[k][x1][y1][x2][y2] = sum(x1, y1, x2, y2);
    if (x1 == x2 && y1 == y2)
        return f[k][x1][y1][x2][y2] = sum(x1, y1, x2, y2);
    int ret = maxint;
    for (int i = x1; i < x2; i++)
    {
        ret <?= dp(k - 1, x1, y1, i, y2) + sum(i + 1, y1, x2, y2);
        ret <?= sum(x1, y1, i, y2) + dp(k - 1, i + 1, y1, x2, y2);
    }
    for (int i = y1; i < y2; i++)
    {
        ret <?= dp(k - 1, x1, y1, x2, i) + sum(x1, i + 1, x2, y2);
        ret <?= sum(x1, y1, x2, i) + dp(k - 1, x1, i + 1, x2, y2);
    }
    return f[k][x1][y1][x2][y2] = ret;
}
 
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= 8; i++)
        for (int j = 1; j <= 8; j++)
            scanf("%d", &a[i][j]);
    memset(g, 0, sizeof(g));
 
    for (int i = 0; i <= 8; i++)
        for (int j = 0; j <= 8; j++)
            g[i][j] = g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1] + a[i][j];
    
    for (int k = 0; k <= 15; k++)
        for (int x1 = 1; x1 <= 8; x1++)
            for (int y1 = 1; y1 <= 8; y1++)
                for (int x2 = 1; x2 <= 8; x2++)
                    for (int y2 = 1; y2 <= 8; y2++)
                        f[k][x1][y1][x2][y2] = maxint;
    
    double sum = 0.0;
    for (int i = 1; i <= 8; i++)
        for (int j = 1; j <= 8; j++)
            sum += a[i][j];
    sum /= n;
    sum *= sum;
 
    printf("%.3lf\n", sqrt(dp(n, 1, 1, 8, 8) / double(n) - sum));
    return 0;
}

相关文章

标签云: , | 日志分类: 动态规划
如需转载烦请添加以下信息: 本文转自Felicia@GCCFeli.cn

  • 评论 (0)
  • 引用通告 (0)
发表评论 引用通告

暂无评论.

暂无引用通告