题意：一个泳池，纵切面是形成一个由N＊M个小方格组成的矩形，一个机器人初始时在(1,1)，它要游到(1, M)，其水平速度为1（恒定），竖直速度为v（可变），至少每K秒到达水面换一次氧气，每个小方格可有变速器vT（会使v + T），也可事先在任意方格放一个speedo，其大小为Q（-1, 0, 1三个数中选一个）（会使v + Q）,vT和Q可同时存在，另外，方格可能会有钱，当机器人到达时，它可获得这些钱（可能是负数），当机器人到达(1, M)时，机器人最多能拥有多少钱（初始时机器人拥有的钱为0）。
1.所有的变速器在最上面一层的格子时全部失效。
2.到达最上面一层的格子时，如果没有speedo，v变为0，有speedo，v变为speedo的值。
3.到达最底的方格时，机器人不停地撞地，其v不变（除非遇到了变速的东西）。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3260
——>>设d[i]表示从(1, 1)到达(1, i)时机器人最多获得了多少钱。。。然后就dfs更新吧。。。（思路源于oyk：http://www.cnblogs.com/oyking/p/3268737.html）
1.不知是不是方法不对，上面的第2点，不理它，能够AC。。。
2.机器人到达某个方格时，如果有钱，它会取，但是从上一个位置到这一个位置过程中经过的点，即使有钱，它也不取。。。
3.纯数字表示超过int，要加上LL，不然会CE的。。。（听说是编译器默认数字的类型为int，单纯地直接写一个超int的数字就溢出了。。。）
过了这题，学了个新的数字0xc0，可用它来赋无穷小，其对应的int是0xc0c0c0c0，对应的long long是0xc0c0c0c0c0c0c0c0LL，如果数组是int的，memset(d, 0xc0, sizeof(d))会将该数组赋成0xc0c0c0c0，如果数组是long long的，同样的memset会将其赋成0xc0c0c0c0c0c0c0c0。。。
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int maxn = 100 + 10;
const int maxm = 1000 + 10;
const long long IINF = 0xc0c0c0c0c0c0c0c0LL;int N, M, K;
char C[maxn][maxm];
int G[maxn][maxm];
long long d[maxm];void dfs(int from, int cur_r, int cur_c, int v, long long sum) {if(cur_r < 1) cur_r = 1;if(cur_r > N) cur_r = N;if(cur_r == 1 && cur_c != from) { //不能少第二个条件，不然一进来就出去了，无法更新其它信息d[cur_c] = max(d[cur_c], sum);return; //下面solve中循环会继续更新}if(cur_c - from == K || cur_c == M) return;if(C[cur_r][cur_c] == '$') sum += G[cur_r][cur_c]; //这个不能放上面，不然就重复计算了else if(cur_r != 1) v += G[cur_r][cur_c];
// if(cur_r == 1) {
// if(Q == 0) v = 0;
// else v = Q;
// }dfs(from, cur_r+v, cur_c+1, v, sum);dfs(from, cur_r+v-1, cur_c+1, v-1, sum);dfs(from, cur_r+v+1, cur_c+1, v+1, sum);
}void read() {for(int i = 1; i <= N; i++)for(int j = 1; j <= M; j++)scanf(" %c%d", &C[i][j], &G[i][j]);
}void solve() {memset(d, 0xc0, sizeof(d));d[1] = 0;for(int i = 1; i <= M; i++) dfs(i, 1, i, 0, d[i]);if(C[1][M] == '$') d[M] += G[1][M];printf("%I64d\n", d[M]);
}int main()
{while(scanf("%d%d%d", &N, &M, &K) == 3) {if(!N && !M && !K) return 0;read();solve();}return 0;
}