2014
01-26

# hdu 2490 Parade-动态规划-[解题报告]C++

When seeing his Citizens, Panagola always waves his hands. He may get tired and need a break. So please never make Panagola travel in a same west-east road for more than k minutes. If it takes p minutes to pass a love-hate zone, we say the length of that love-hate zone is p. Of course you know every love-hate zone’s length.

The figure below illustrates the case in sample input. In this figure, a best route is marked by thicker lines.

There are multiple test cases. Input ends with a line containing three zeros.
Each test case consists of 2×n + 3 lines.

The first line contains three integers: n, m and k.(0<n<=100,0<m<=10000, 0<=k<=3000000)

The next n+1 lines stands for n + 1 west-east roads in north to south order. Each line contains m integers showing the welcome values of the road’s m love-hate zones, in west to east order.

The last n+1 lines also stands for n + 1 west-east roads in north to south order. Each line contains m integers showing the lengths (in minutes) of the road’s m love-hate zones, in west to east order.

There are multiple test cases. Input ends with a line containing three zeros.
Each test case consists of 2×n + 3 lines.

The first line contains three integers: n, m and k.(0<n<=100,0<m<=10000, 0<=k<=3000000)

The next n+1 lines stands for n + 1 west-east roads in north to south order. Each line contains m integers showing the welcome values of the road’s m love-hate zones, in west to east order.

The last n+1 lines also stands for n + 1 west-east roads in north to south order. Each line contains m integers showing the lengths (in minutes) of the road’s m love-hate zones, in west to east order.

2 3 2
7 8 1
4 5 6
1 2 3
1 1 1
1 1 1
1 1 1
0 0 0

27

Description

When seeing his Citizens, Panagola always waves his hands. He may get tired and need a break. So please never make Panagola travel in a same west-east road for more than k minutes. If it takes p minutes to pass a love-hate zone, we say the length of that love-hate zone is p. Of course you know every love-hate zone’s length.

The figure below illustrates the case in sample input. In this figure, a best route is marked by thicker lines.

Input

There are multiple test cases. Input ends with a line containing three zeros.  Each test case consists of 2×n + 3 lines.
The first line contains three integers: n, m and k.(0<n<=100,0<m<=10000, 0<=k<=3000000)
The next n+1 lines stands for n + 1 west-east roads in north to south order. Each line contains m integers showing the welcome values of the road’s m love-hate zones, in west to east order.
The last n+1 lines also stands for n + 1 west-east roads in north to south order. Each line contains m integers showing the lengths (in minutes) of the road’s m love-hate zones, in west to east order.

Output

For each test case, output the sum of welcome values of the best route. The answer can be fit in a 32 bits integer.

题目大意：有一个n*m的矩阵，只能沿着边走，只能往左、往右或往上走，在同一行只能沿一个方向走（走了左边就不能返回走右边了）。打横的边都有一个权值（可能为负数）和一个长度，每行走过的长度不能超过k，打竖的边没有权值和长度。先要从最下面的任意一个点开始，走到最上面的任意一个点，问最大权值和为多少（答案不超过2^32-1，虽然题目不是这么说的）。

PS：可恶这题居然不让人在线非要我把整个矩阵一起读进来……

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 110;
const int MAXM = 10010;

int wel[MAXN][MAXM], len[MAXN][MAXM];
int sum_w[MAXM], sum_l[MAXM];
int a[MAXM], b[MAXM], head, tail;
int dp[2][MAXM];
int n, m, k, cur;

inline void insert(int x, int y) {
while(head != tail && a[tail - 1] < x) --tail;
a[tail] = x; b[tail] = y; ++tail;
}

void solve() {
memset(dp, 0, sizeof(dp));
cur = 0;
for(int i = 0; i < n; ++i) {
cur ^= 1;
memset(dp[cur], 0, sizeof(dp[cur]));

sum_w[0] = sum_l[0] = 0;
for(int j = 1; j <= m; ++j) sum_w[j] = sum_w[j - 1] + wel[i][j];
for(int j = 1; j <= m; ++j) sum_l[j] = sum_l[j - 1] + len[i][j];
head = tail = 0;
for(int j = 0; j <= m; ++j) {
insert(dp[cur ^ 1][j] - sum_w[j], sum_l[j]);
dp[cur][j] = max(dp[cur][j], a[head] + sum_w[j]);
}

sum_w[m] = sum_l[m] = 0;
for(int j = m; j > 0; --j) sum_w[j - 1] = sum_w[j] + wel[i][j];
for(int j = m; j > 0; --j) sum_l[j - 1] = sum_l[j] + len[i][j];
head = tail = 0;
for(int j = m; j >= 0; --j) {
insert(dp[cur ^ 1][j] - sum_w[j], sum_l[j]);
dp[cur][j] = max(dp[cur][j], a[head] + sum_w[j]);
}
}
}

int main() {
while(scanf("%d%d%d", &n, &m, &k) != EOF) {
if(n == 0 && m == 0 && k == 0) break;
++n;
for(int i = 0; i < n; ++i)
for(int j = 1; j <= m; ++j) scanf("%d", &wel[i][j]);
for(int i = 0; i < n; ++i)
for(int j = 1; j <= m; ++j) scanf("%d", &len[i][j]);
solve();
int ans = 0;
for(int i = 0; i <= m; ++i) ans = max(ans, dp[cur][i]);
printf("%d\n", ans);
}
}

1. L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）这个地方也也有笔误
应改为L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-2]）