转眼间，2015说再见了，2016来到了，过去的一年是难忘的一年，在这一年，我家宝宝开始流利的学说话了，我来到了美国University of Illinois at Urbana-Champaign交流访问。进入2016，自己也马上34岁了。想一想沉甸甸的。从自己2011年毕业，马上要5个年头了。5年经历了很多，有胜利也有挫折，带着这些财富，我将如何规划自己的未来。我自己内心的追求是什么？毫无疑问，我热爱自己的教学科研，正如过去所说，通过教学科研培养有进取心的好学生和做出实在的一些研究成果，促进社会的发展。我要名利吗？名利对每个人多很重要，名利是和每个人的收入和生活质量息息相关，但是过去的5年，我亲自耳闻目睹很多名利双收的拥有各种头衔的真牛人和假牛人，也的确遇见很多“默默无闻“的长者，他们没有那么多的头衔，收入也不多，但是他们却是也在努力真真正正做学问。 我将努力成为哪一类人？......很多东西不是自己决定的，而唯一能自己决定的就是做好自己，做真实的自己，做自己想做的事情。至于能成为哪一类，对于自己，这是自然的事情，不应过度去解读这些。自己应该做的事踏踏实实，坚守自己的信念和原则。除此之外，人生不仅仅是工作，科研不应成为自己的全部，人生的价值包括很多。虽然科研不同于其他职业，但是生活是丰富多彩的，人生应该是方方面面的。做自己，走自己的路，才是根本。至于外界所给的名利，有则有，无则无，并非是必需的，因为名利带来的很多钱财并非是小康生活所必需的。健康、幸福和自我内心的追求和真实的成功才是根本。自我顿时豁然开朗，不要愤愤不平他人不好之所为，不要过分在意这些名利的身外东西，因为任何事情都是需要付出代价的。自己应该所做的是：带着一颗永远积极的心，健康快乐生活、努力踏实坚定做自己的事情。即使风雨交加，都是一种人生的财富和经历。走适合自己的路，让别人去说吧。屠呦呦，一位普通的科研工作者，不管很多国内同行曾对她非议过什么，评论过什么，终究她是第一位获得诺贝尔医学奖的中国人，这是中国人的自豪！当然，估计屠老对这个身外的荣誉已经看得很开了，有则喜，无则坦然。 2016， 我们来了。
Problem Jeff loves playing games, Gluttonous snake( an old game in NOKIA era ) is one of his favourites. However, after playing gluttonous snake so many times, he finally got bored with the original rules. In order to bring new challenge to this old game, Jeff introduced new rules : The ground is a grid, with n rows and m columns(1 = n, m = 500). Each cell contains a value v (-1 ≤ vi≤ 99999), if v is -1, then this cell is blocked, and the snake can not go through, otherwise, after the snake visited this cell, you can get v point. The snake can start from any cell along the left border of this ground and travel until it finally stops at one cell in the right border. During this trip, the snake can only go up/down/right, and can visit each cell only once. Special cases : Even in the left border and right border, the snake can go up and down When the snake is at the top cell of one column, it can still go up, which demands the player to pay all current points , then the snake will be teleported to the bottom cell of this column and vice versa. After creating such a new game, Jeff is confused how to get the highest score. Please help him to write a program to solve this problem. Input The first line contains two integers n (rows) and m (columns), (1 = n, m = 500), separated by a single space. Next n lines describe the grid. Each line contains m integers vi (-1 ≤ vi ≤ 99999) vi = -1 means the cell is blocked. Output Output the highest score you can get. If the snake can not reach the right side, output -1. Sample Test input 4 4 -1 4 5 1 2 -1 2 4 3 3 -1 3 4 2 1 2 4 4 -1 4 5 1 2 -1 2 4 3 3 -1 -1 4 2 1 2 output 23 16 Solution 1 思路 直接使用回溯法，用grid 表示每个点的值，用vis 表示每个点是否访问。该方法比较简单直观，不做多说。 代码 #include iostream #include cstring #include cstdio #include vector #include cmath #include map #include algorithm using namespace std ; int grid ; bool vis ; int m, n; long long ans = - 1 ; int cx = { 0 , 1 , 0 }; void dfs( long long sum, int x, int y) { if (y == n - 1 sum ans) { ans = sum; } for ( int i = 0 ; i 3 ; ++i) { bool flag = false ; int nx = x + cx ; if (nx == - 1 ) { nx = m - 1 ; flag = true ; } if (nx == m) { nx = 0 ; flag = true ; } int ny = y + cy ; if (ny == n) continue ; if (vis || grid == - 1 ) continue ; vis = true ; if (flag) dfs(grid , nx, ny); else dfs(sum + grid , nx, ny); vis = false ; }} int main() { scanf ( %d%d , m, n); for ( int i = 0 ; i m; ++i) for ( int j = 0 ; j n; ++j) scanf ( %d , grid ); memset (vis, false , sizeof (vis)); for ( int i = 0 ; i m; ++i) { if (grid == - 1 ) continue ; vis = true ; dfs(grid , i, 0 ); vis = false ; } printf ( %lld\n , ans); return 0 ;} 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 Solution 2 思路 使用回溯法，虽然简单容易理解，但是数据量太大容易爆栈。这题还可以使用动态规划求解。使用grid 表示每个点的值，使用dp 表示从点 为起点不穿越取得的最大值，dp 表示从点 为起点有穿越取得的最大值。那么状态转移方程为： 当在j列不穿越： dp = max(dp + sumk) dp = max(dp ) 当在j列有穿越： dp = max(dp + sumk’) dp = max(dp ) 上面的转移方程没有考虑特殊情况。 有点复杂，可能看不大懂，还是直接上代码吧，看代码注释应该容易懂很多。 代码 #include iostream #include cstring #include cstdio #include vector #include cmath #include map #include algorithm using namespace std; int grid ; long long dp ; //dp 表示从 点开始不穿越能取到的最大值 //dp 表示从 点开始穿越能取到的最大值 int m, n; int main() { scanf( %d%d , m, n); for ( int i = 0 ; i m; ++i) for ( int j = 0 ; j n; ++j) scanf( %d , grid ); memset(dp, 0 , sizeof(dp)); long long sum , ans1, ans2; bool flag; for ( int j = n - 1 ; j = 0 ; --j) { for ( int i = 0 ; i m; ++i) { sum = 0 ; if (grid == - 1 ) { //该点不可到达 dp = dp = - 1 ; continue ; } ans1 = - 1 ; //记录不穿越的最大值 ans2 = - 1 ; //记录穿越的最大值 flag = false ; //记录是否碰到不可到达的点 //往上走 for ( int k = i; k = 0 ; --k) { if (grid == - 1 ) { flag = true ; break ; } sum += grid ; //在当前列未穿越 if (dp != - 1 dp + sum ans1) ans1 = dp + sum ; //如果取后面的穿越最大值，那么前面的sum全部清0 if (dp != - 1 dp ans2) ans2 = dp ; } if (!flag) { sum = 0 ; for ( int k = m - 1 ; k i; --k) { if (grid == - 1 ) { flag = true ; break ; } sum += grid ; //在当前列有穿越 if (dp != - 1 dp + sum ans2) ans2 = dp + sum ; if (dp != - 1 dp ans2) ans2 = dp ; } } //往下走 sum = 0 ; flag = false ; for ( int k = i; k m; ++k) { if (grid == - 1 ) { flag = true ; break ; } sum += grid ; if (dp != - 1 dp + sum ans1) ans1 = dp + sum ; if (dp != - 1 dp ans2) ans2 = dp ; } if (!flag) { sum = 0 ; for ( int k = 0 ; k i; ++k) { if (grid == - 1 ) { flag = true ; break ; } sum += grid ; if (dp != - 1 dp + sum ans2) ans2 = dp + sum ; if (dp != - 1 dp ans2) ans2 = dp ; } } dp = ans1; dp = ans2; } } //查询最大值 long long ans = - 1 ; for ( int i = 0 ; i m; ++i) { if (dp ans) ans = dp ; if (dp ans) ans = dp ; } printf( %lld\n , ans); return 0 ;} ---转自 wangtaoking1 的CSDN博客
标签: 2016
