Climber.pI的OI之路

Through the darkest dark,may we see the light.

NOIp 2008 传纸条

和2000的方格取数如出一辙.数据加强了一点,如果是裸的四维dp可能会超时(80).所以需要优化.

1.普通的四维做法

【状态】f[x1][y1][x2][y2] 表示从出发点分别到(x1,y1)、(x2,y2)取的最大值.G[x][y]表示该格的数.

【方程】f[x1][y1][x2][y2] = max{f[x1-1][y1][x2-1][y2],f[x1-1][y1][x2][y2-1],f[x1][y1-1][x2-1][y2],f[x1][y1-1][x2][y2-1]}+G[x1][y1]+G[x2][y2](如果位置不重复)

【一个重要优化】显然有y2=x1+y1-x2(y2>0),因而时间复杂度可以降到O(n^3).Cena显示总用时从近4s降到近0.3s,效果明显.

2.三维做法(参考官方题解)

【状态】f[p][x1][x2],p表示经过的格子数.

【方程】f[p][x1][x2]=max{f[p-1][x1-1][x2-1],f[p-1][x1-1][x2],f[p-1][x1][x2-1],f[p-1][x1][x2]}+G[x1][p-x1]+G[x2][p-x2](如果位置不重复)

未编程验证.

3.更优化的做法

dy神牛指出,进一步的优化需要用到最小费用最大流.(NOIP绝对超纲,可以确定不会更深了.)

【Code】

 

1 #include<stdio.h>
2 #include<iostream>
3 using namespace std;
4 int f[52][52][52][52] = {0}, n, G[52][52];
5 int max(int a, int b, int c, int d){
6     if (a < b) a= b;
7     if (a < c) a= c;
8     if (a < d) a= d;
9     return a;
10 }
11 int main(){
12     int m, n, i, j, k, l;
13     scanf("%d%d", &m, &n);
14     for (i = 1; i <= m; i++)
15         for (j = 1; j <= n; j++)
16             scanf("%d", &G[i][j]);
17     for (i = 1; i <= m; i++)
18         for (j = 1; j <= n; j++)
19             for (k = 1; k <= m; k++){
20                     if (i+j-k > 0) l = i+j-k; else continue;
21                     f[i][j][k][l] = max(f[i-1][j][k-1][l], f[i-1][j][k][l-1], f[i][j-1][k-1][l], f[i][j-1][k][l-1])+G[i][j]+G[k][l];
22                     if (i == k && j == l) f[i][j][k][l] -= G[i][j];
23                 }
24     printf("%d\n", f[m][n][m][n]);
25 }
26 

posted on 2010-10-02 22:28 Climber.pI 阅读(2491) 评论(1)  编辑 收藏 引用 所属分类: 动态规划

Feedback

# re: NOIp 2008 传纸条[未登录] 2013-05-14 13:12 x

xx  回复  更多评论   


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