May the force be with you!
posts - 52,  comments - 33,  trackbacks - 0
《算法艺术与信息学竞赛》P-116:
提交方式:POJ1191
好久没有写文章了,随便放一个题目在这里凑数:

题目描述:

棋盘分割
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 1302
Accepted: 463

Description
将一个8*8的棋盘进行如下分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将剩下的部分继续如此分割,这样割了(n-1)次后,连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)


原棋盘上每一格有一个分值,一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘,并使各矩形棋盘总分的均方差最小。
均方差,其中平均值,xi为第i块矩形棋盘的总分。
请编程对给出的棋盘及n,求出O'的最小值。

Input
第1行为一个整数n(1 < n < 15)。
第2行至第9行每行为8个小于100的非负整数,表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

Output
仅一个数,为O'(四舍五入精确到小数点后三位)。

Sample Input

3
1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 3

Sample Output

1.633

Source
Noi 99


解题思路:

参照《算法艺术与信息学竞赛》:


代码:

  1 /*********************************************************************
  2 Author: littlekid
  3 Created Time: 2008-2-27 17:08:36
  4 Problem Source: POJ1191
  5 Description: 
  6 ********************************************************************/
  7 # include <iostream>
  8 # include <cmath>
  9 using namespace std;
 10 
 11 const int maxint = 2000000000;
 12 
 13 # define N 8
 14 
 15 double ans;
 16 int map[ N+1 ][ N+1 ], n;
 17 int sum[ N+1 ][ N+1 ];//[ N+1 ][ N+1 ];
 18 int f[16][ N+1 ][ N+1 ][ N+1 ][ N+1 ];
 19 
 20 void init()
 21 {
 22     for (int i = 1; i <= N; i ++)
 23     {
 24         for (int j = 1; j <= N; j++)
 25         {
 26             scanf("%d"&map[i][j]);
 27         }
 28     }
 29 }
 30 
 31 void output()
 32 {
 33     printf("%.3lf\n", ans);
 34 }
 35 
 36 inline int cal_sum(int x1, int y1, int x2, int y2)
 37 {
 38     int tmp = sum[x2][y2]+sum[x1-1][y1-1- sum[x1-1][y2]-sum[x2][y1-1];
 39     return tmp*tmp;
 40 }
 41 
 42 
 43 void dp()
 44 {
 45     //
 46     memset(sum, 0, sizeof(sum));
 47     int tmp;
 48     sum[0][0= 0;
 49      for (int i = 1; i <= N; i ++)
 50     {
 51         for (int j = 1; j <= N; j ++)
 52         {
 53             sum[i][j] = sum[i][j-1]+sum[i-1][j] - sum[i-1][j-1+ map[i][j];
 54         }
 55     }
 56     memset(f, 0, sizeof(f));
 57     for(int x1 = 1; x1 <= N; x1 ++)
 58     {
 59         for (int y1 = 1; y1 <= N; y1 ++)
 60         {
 61             for (int x2 = x1; x2 <= N; x2 ++)
 62             {
 63                 for (int y2 = y1; y2 <= N; y2 ++)
 64                 {
 65                     f[1][x1][y1][x2][y2] = cal_sum(x1, y1, x2, y2);
 66                 }
 67             }
 68         }
 69     }
 70     for (int k = 2; k <= n; k ++)
 71     {
 72 
 73         for (int x1 = 1; x1 <= N; x1 ++)
 74         {
 75             for (int y1 = 1; y1 <= N; y1 ++)
 76             {
 77                 for (int x2 = x1; x2 <= N; x2 ++)
 78                 {
 79                     for (int y2 = y1; y2 <= N; y2 ++)
 80                     {
 81 
 82                         f[k][x1][y1][x2][y2] = maxint;
 83                         for (int x = x1; x < x2; x ++)
 84                         {
 85                             tmp = min( f[k-1][x1][y1][x][y2] + cal_sum(x+1, y1, x2, y2), //sum[x+1][y1][x2][y2],
 86                                        f[k-1][x+1][y1][x2][y2] + cal_sum(x1, y1, x, y2)); //sum[x1][y1][x][y2] );
 87                             if (f[k][x1][y1][x2][y2] > tmp) f[k][x1][y1][x2][y2] = tmp;
 88                         }
 89                         for (int y = y1; y < y2; y ++)
 90                         {
 91                             tmp = min( f[k-1][x1][y1][x2][y] + cal_sum(x1, y+1, x2, y2), //sum[x1][y+1][x2][y2],
 92                                        f[k-1][x1][y+1][x2][y2] + cal_sum(x1, y1, x2, y) ); //sum[x1][y1][x2][y] );
 93                             if (f[k][x1][y1][x2][y2] > tmp) f[k][x1][y1][x2][y2] = tmp;
 94 
                        }
 95                     }
 96                 }
 97             }
 98         }
 99     }
100 //    cout << f[n][1][1][N][N] << endl; ///
101     ans = sqrt( f[n][1][1][N][N]/(double)n - sum[N][N]*sum[N][N]/(double)(n*n));
102 }
103 
104 int main()
105 {
106     while (scanf("%d"&n) != EOF)
107     {
108         init();
109         dp();
110         output();
111     }
112     return 0;
113 }
114 
115 

 



posted on 2008-02-27 20:04 R2 阅读(1926) 评论(1)  编辑 收藏 引用 所属分类: Problem Solving

FeedBack:
# re: 【DP】PKU1191棋盘分割问题解题报告
2009-01-22 17:09 | 小菜
我的代码和大牛的差不多,怎么就是wa个不停呀?
#include <stdio.h>
#include <string.h>
#include <math.h>
int min(int a, int b)
{
return a<b?a:b;
}

int main()
{
int n, q[9][9]={0}, i, j, k, l, m, s[9][9], d[15][9][9][9][9], a, b;
double ans;
while(scanf("%d",&n)==1)
{
memset(s,0,sizeof(s));
memset(q,0,sizeof(q));
for(i=1;i<=8;i++)
for(j=1;j<=8;j++)
scanf("%d",&q[i][j]);
for(i=1;i<=8;i++)
for(j=1;j<=8;j++)
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+q[i][j];
//d[k][x1][y1][x2][y2]=min{d[k-1][x1][y1][a][y2]+f[a+1][y1][x2][y2],d[k-1][a+1][y1][x2][y2]+f[x1][y1][a][y2]}(x1<=a<x2)
// min{d[k-1][x1][y1][x2][b]+f[x1][b+1][x2][y2],d[k-1][x1][b+1][x2][y2]+f[x1][y1][x2][b]}(y1<=b<y2)
//d[1][x1][y1][x2][y2]=s[x2][y2]+s[x1-1][y1-1]-s[x1-1][y2]-s[x2][y1-1]
for(i=1;i<=8;i++)
for(j=1;j<=8;j++)
for(k=i;k<=8;k++)
for(l=j;l<=8;l++)
d[1][i][j][k][l]=(s[k][l]+s[i-1][j-1]-s[i-1][l]-s[k][j-1])*(s[k][l]+s[i-1][j-1]-s[i-1][l]-s[k][j-1]);
for(i=2;i<=n;i++)
{
for(j=1;j<=8;j++)
for(k=1;k<=8;k++)
for(l=j;l<=8;l++)
for(m=k;m<=8;m++)
{
d[i][j][k][l][m]=0x7fffffff;
for(a=j;a<l;a++)
{
d[i][j][k][l][m]=min(d[i-1][j][k][a][m]+d[1][a+1][k][l][m],d[i][j][k][l][m]);
d[i][j][k][l][m]=min(d[i-1][a+1][k][l][m]+d[1][j][k][a][m],d[i][j][k][l][m]);
}
for(b=k;b<m;b++)
{
d[i][j][k][l][m]=min(d[i-1][j][k][l][b]+d[1][j][b+1][l][m],d[i][j][k][l][m]);
d[i][j][k][l][m]=min(d[i-1][j][b+1][l][m]+d[1][j][k][l][b],d[i][j][k][l][m]);
}
}
}
ans=sqrt(d[n][1][1][8][8]/(double)n-(s[8][8]/(double)n)*(s[8][8]/(double)n));
printf("%.3lf\n",ans);
}
return 0;
}
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


你是第 free hit counter 位访客




<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(4)

随笔分类(54)

随笔档案(52)

文章档案(1)

ACM/ICPC

技术综合

最新随笔

搜索

  •  

积分与排名

  • 积分 - 61528
  • 排名 - 357

最新评论

阅读排行榜

评论排行榜