- 浏览: 36177 次
文章分类
- 全部博客 (41)
- 卧鸟个去 (2)
- Transform (2)
- Mathmatic (9)
- Plant-Tree (7)
- Data-Struct (12)
- Red-Black-Tree (1)
- Radix-Tree (1)
- Trie (2)
- String (4)
- BST (2)
- Amazing-Union-Find-Set (1)
- HDU (27)
- OJ (32)
- BFS (3)
- Pretty-Suffix-Array (2)
- POJ (6)
- Graceful-Segment-Tree (2)
- Geometry (6)
- Priority-Queue (2)
- Dynamic-Programing (1)
- DP (3)
- LCS (1)
- Convex-Hull (2)
- Triangulation (1)
- DFS (3)
- Combinatorial-Mathematics (2)
- Big-Number (1)
- Statistic (3)
- STL (1)
- Shortest-Path (3)
- ZOJ (1)
- Leftist-Tree (1)
- Prime (1)
- Binary-Index-Tree (1)
- (1)
- Stack (1)
- SPFA (0)
- CRT (1)
命运
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 9 Accepted Submission(s) : 4
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
穿过幽谷意味着离大魔王lemon已经无限接近了!
可谁能想到,yifenfei在斩杀了一些虾兵蟹将后,却再次面临命运大迷宫的考验,这是魔王lemon设下的又一个机关。要知道,不论何人,若在迷宫中被困1小时以上,则必死无疑!
可怜的yifenfei为了去救MM,义无返顾地跳进了迷宫。让我们一起帮帮执着的他吧!
命运大迷宫可以看成是一个两维的方格阵列,如下图所示:
yifenfei一开始在左上角,目的当然是到达右下角的大魔王所在地。迷宫的每一个格子都受到幸运女神眷恋或者痛苦魔王的诅咒,所以每个格子都对应一个值,走到那里便自动得到了对应的值。
现在规定yifenfei只能向右或者向下走,向下一次只能走一格。但是如果向右走,则每次可以走一格或者走到该行的列数是当前所在列数倍数的格子,即:如果当前格子是(x,y),下一步可以是(x+1,y),(x,y+1)或者(x,y*k) 其中k>1。
为了能够最大把握的消灭魔王lemon,yifenfei希望能够在这个命运大迷宫中得到最大的幸运值。
可谁能想到,yifenfei在斩杀了一些虾兵蟹将后,却再次面临命运大迷宫的考验,这是魔王lemon设下的又一个机关。要知道,不论何人,若在迷宫中被困1小时以上,则必死无疑!
可怜的yifenfei为了去救MM,义无返顾地跳进了迷宫。让我们一起帮帮执着的他吧!
命运大迷宫可以看成是一个两维的方格阵列,如下图所示:
yifenfei一开始在左上角,目的当然是到达右下角的大魔王所在地。迷宫的每一个格子都受到幸运女神眷恋或者痛苦魔王的诅咒,所以每个格子都对应一个值,走到那里便自动得到了对应的值。
现在规定yifenfei只能向右或者向下走,向下一次只能走一格。但是如果向右走,则每次可以走一格或者走到该行的列数是当前所在列数倍数的格子,即:如果当前格子是(x,y),下一步可以是(x+1,y),(x,y+1)或者(x,y*k) 其中k>1。
为了能够最大把握的消灭魔王lemon,yifenfei希望能够在这个命运大迷宫中得到最大的幸运值。
Input
输入数据首先是一个整数C,表示测试数据的组数。
每组测试数据的第一行是两个整数n,m,分别表示行数和列数(1<=n<=20,10<=m<=1000);
接着是n行数据,每行包含m个整数,表示n行m列的格子对应的幸运值K ( |k|<100 )。
每组测试数据的第一行是两个整数n,m,分别表示行数和列数(1<=n<=20,10<=m<=1000);
接着是n行数据,每行包含m个整数,表示n行m列的格子对应的幸运值K ( |k|<100 )。
Output
请对应每组测试数据输出一个整数,表示yifenfei可以得到的最大幸运值。
Sample Input
1 3 8 9 10 10 10 10 -10 10 10 10 -11 -1 0 2 11 10 -20 -11 -11 10 11 2 10 -10 -10
Sample Output
52
Author
yifenfei
Source
ACM程序设计期末考试081230
呢类DP题目我地呢度通常称为数塔题,因为基本上都系同一个模型只不过走法多左一种甘解,都几容易写出状态转移方程{= =+}。
注意题目提到有三种走法:
假设当前位置为(x, y), 矩阵大小为[n][ m],
1、可以走向(x + 1 ,y)。
2、可以走向(x, y + 1)。(第一次测试果阵发觉答案错左,原来漏了呢种可能)
3、可以走向(x, y * k)其中y * k <= m且k > 1。(无左呢个就系数塔问题鸟)
所以状态转移方程就系:
dp[x][y] = Max(dp[x - 1][y], dp[x][y - 1], {dp[x][y / k] | 1 < k <= y})
我写法类似最短路既松弛技术,即系顺推用一个临时数组储存当前比较值,由当前点出发有(1 + 1 + k)条路每条路都松弛一下,时间复杂
度都相似,大概O(n*m*∑k)吧。
下面写代码{= =}
00762067 | 2011-07-20 14:19:17 | Accepted | 1009 | 15 MS | 388 KB | Visual C++ | 10SGetEternal{(。) |
#include <iostream> using namespace std; #define XMAX 22 #define YMAX 1001 #define INFI ((1<<31) - 1) int n, m, map[XMAX][YMAX], ts[XMAX][YMAX]; void print(int *arr, int siz) { int i; for (i = 1; i <= siz; i++) printf(arr[i] == -INFI?"-INFI ":"%6d ", arr[i]); putchar('\n'); } void init() { int i,j; for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) ts[i][j] = -INFI; } int dp() { int i, j, k; ts[1][1] = 0; for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) { ts[i][j] += map[i][j]; for (k = 2; k * j <= m; k++) if (ts[i][j] > ts[i][k * j]) ts[i][k * j] = ts[i][j]; if (i < n && ts[i][j] > ts[i + 1][j]) ts[i + 1][j] = ts[i][j]; if (j < m && ts[i][j] > ts[i][j + 1]) ts[i][j + 1] = ts[i][j]; } return ts[n][m]; } int main() { int C, i, j; scanf("%d", &C); while (C--) { scanf("%d%d", &n, &m); for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) scanf("%d", map[i] + j); #if 0 for (i = 1; i <= n; i++) print(map[i], m); #endif init(); #if 0 for (i = 1; i <= n; i++) print(ts[i], m); #endif printf("%d\n", dp()); #if 0 for (i = 1; i <= n; i++) print(ts[i], m); #endif } return 0; }
多谢收睇{^ _____^}
发表评论
-
HDU 1370 Biorhythms
2011-08-03 10:27 1159Biorhythms Time Limit: 2000/10 ... -
HDU 1075 What Are You Talking About
2011-08-04 11:00 838What Are You Talking About Tim ... -
HDU 1058 Humble Numbers
2011-08-02 15:55 1175Humble Numbers Time Limit: 200 ... -
HDU 2095 find your present (2)
2011-08-02 16:13 770find your present (2) Time Lim ... -
HDU 1022 Train Problem I
2011-08-02 21:00 999Train Problem I Time Limit: 20 ... -
2142 HDU box
2011-08-02 21:21 736box Time Limit: 3000/1000 MS ( ... -
HDU 2151 Worm
2011-08-01 20:48 793Worm Time Limit: 1000/1000 MS ... -
HDU 2722 Here We Go(relians) Again
2011-08-02 00:06 973Here We Go(relians) Again Time ... -
HDU 3791 二叉搜索树
2011-08-02 14:26 1164二叉搜索树 Time Limit: 20 ... -
PKU 2352 Stars
2011-07-31 21:47 989Stars Time Limit: 1000MS ... -
PKU 2774 Long Long Message
2011-07-31 21:26 867Long Long Message Time Li ... -
PKU 2777 Count Color
2011-07-31 21:31 770Count Color Time Limit: 1 ... -
HDU 2098 分拆素数和
2011-07-31 21:08 1017分拆素数和 Time Limit: 1000/1000 MS ... -
ZOJ 3512 Financial Fraud .
2011-07-31 20:49 1233Financial Fraud Time Limit: 3 ... -
HDU 1798 Tell me the area .
2011-07-31 20:47 1075Tell me the area Time Limit: 3 ... -
HDU 2962 Trucking .
2011-07-31 20:46 644Trucking Time Limit: 20000/100 ... -
HDU 1596 find the safest road .
2011-07-31 20:45 575find the safest road Time Limi ... -
HDU 2553 N皇后问题 .
2011-07-31 20:20 668N皇后问题 Time Limit: 2000/1000 MS ... -
HDU 1392 Surround the Trees .
2011-07-31 20:19 763Surround the Trees Time Limit: ... -
HDU 1234 开门人和关门人 .
2011-07-31 20:17 644开门人和关门人 Time Limit: 2000/1000 ...
相关推荐
hdu 乒乓 裁判.
此程序为hdu的acm2010题,就是解决水仙花数问题
杭电hdu acm资料所用杭电的acm题
Hdu 1020解题报告,http://acm.hdu.edu.cn/showproblem.php?pid=1020
本压缩包内包含杭电ACM集训的课件PPT,较为详细的介绍了动态规划,计算几何,贪心算法, 搜索,二分图及其应用,母函数及其应用,组合博弈入门,并查集,递推求解等常用算法
liudongjun-hdu.github.io
ACM HDU题目分类,我自己总结的大概只有十来个吧
next[i]的含义是在str[i]之前的字符串str[0...i]中,必须以str[i-1]结尾的后缀子串(不能包含str[0])与必须以str[0]开头的前
杭电OJ部分答案,可以很简单的解决a+b求和问题及其他问题。
算法-命运(HDU-2571)(包含源程序).rar
HDU ACM 2005第几天 C++ http://acm.hdu.edu.cn/listproblem.php?vol=11 2005题 第几天?
计算机网络复习大纲_杭电hdu借鉴.pdf
计算机网络复习大纲_杭电hdu整理.pdf
计算机网络复习大纲_杭电hdu参考.pdf
HDU的一题........HDU DP动态规
HDU一部分题目原码,大部分是可运行的,可能有几题不完整
算术(HDU-6715).rar