Problem E - Bridge Building
Against the city's gleaming spires,
Above the ships that ply the stream,
A bridge of haunting beauty stands -
Fulfillment of an artist's dream
(D. B. Steinman)
Algorithm city is crossed by the beautiful Complexity River. Up
until now, the only possible way to travel from one bank (margin) of the river
to the other is by boat. This is very negative for the city economics
and therefore the mayor has decided to build a series of bridges to
connect the two parts of the city, lying on different banks of the river.
He has a fixed number of bridges to build, but in order to save the
maximum amount of money he wishes to build the bridges has short as possible.
However, since he wants to really help the citizens, the bridges must not be
to close together, in order to have them splitted all over the city.
The mayor has asked for your help, and has given
you the map of the part of city with that is near the river. To simplify,
this map can be seen as a grid of chars. '#' means a piece of
terrain and '.' means water. So, for example, a map could be something
like:
####################
..######........##..
....##..............
....................
....................
.................#..
..######........##..
####################
Figure 1 - An example of a valid map
You can be sure that the map will always have
terrain-only on the first and last rows, and that those pieces of
terrain correspond
to different banks. There will be no islands in the river, and all terrain
will either be connected to the north or south bank. We consider a piece
of terrain to be connected to another if they are adjacent, that is,
if they are next to each other horizontally or vertically (but not
diagonally). You can also be sure that on the same column of the grid map,
there will never be a south piece of the bank above a north
one. However, small lakes (that do not belong to the river) can exist
inside banks, as exemplified in figure 2.
###############
.#..#.......#..
.####......##..
.####..........
.#........##...
..........#....
###############
Figure 2 - Another example of a valid map
The Algorithm City mayor is very old fashioned and has decided that the
bridges to build must only be built in the north-south direction (vertically,
in the grid). So, for example, imagine that the mayor would like to build
3 bridges, that must be separated at least by 4 positions, on the map of
the figure 1. A solution that would minimize the length of the bridges
would be the one in figure 3, where 'B' represents a bridge.
####################
..######........##..
..B.##.B.........B..
..B....B.........B..
..B....B.........B..
..B....B.........#..
..######........##..
####################
Figure 3 - A solution for the map of figure 1
Note that the first two bridges in the solution are exactly separated by
4 spaces as required, and could not be more close. If we measure the length
of the bridges built by squares in the grid, we can say that the total
length used was 11 (4+4+3). Any other way of building the bridges in this map
would give more total length and therefore would be worse.
The Problem
Given a grid map as specified above, a number of bridges to build and
the minimum space (on columns) that should separate the bridges, your task is
to calculate the best positions to build the bridges in order to minimize
their total length, and print the total length of the bridges in that
best arrangement.
Input
The input file contains several test cases, each of them as describes below.
The first line of input contains two integers,
R and C, representing respectively the numbers of rows
and the number of columns of the grid map (5 ≤ R,C ≤ 1000).
Then comes a line with two integers, B and S, where
B represents the number of bridges to build (1 ≤ B &le 100)
and S the minimum space (in columns) that should separate bridges.
After that come exactly R lines, each one with C chars,
that represent the map. This map obeys to the rules described above
and only has '#' or '.'.
Output
For each test case, the output should contain a single line, with an integer representing
the total length of bridges to build in the solution that minimizes this same
total, as described above.
There will always be a way to build the bridges.
Sample Input
8 20
3 4
####################
..######........##..
....##..............
....................
....................
.................#..
..######........##..
####################
7 15
2 8
###############
.#..#.......#..
.####......##..
.####..........
.#........##...
..........#....
###############
Sample Output
11
2
2006 Programming Contest of Porto University
Round 3, 11th of October of 2006
(Author: Pedro Ribeiro - DCC/FCUP)
題目描述：
在一個 R*C 的地圖中，只有上(北)方陸地和下(南)方陸地，打算建造 B 座橋梁，
保證不會存在有北方陸地在南方陸地的南方，即不會有螺旋的樣子。
而每座橋梁只會筆直地由南到北，橋梁與橋梁之間至少間隔 S 格。
問最少成本(每座橋梁的長度總和)為何？
題目解法：
首先先找到每個位置的橋梁的最少成本。
然後 dp[i][j] 表示在位置 i 時，已經建造了 j 座橋梁。
此時 dp[i][j] = cost + min(dp[k][j-1]), 其中 k < i-S
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
char g[1005][1005], used[1005][1005];
int dp[1005][1005], supdp[1005];
int north[1005], south[1005];
int R, C, B, S;
void color(int x, int y, int flag) {
queue<int> X, Y;
int tx, ty, i;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
X.push(x), Y.push(y);
while(!X.empty()) {
x = X.front(), X.pop();
y = Y.front(), Y.pop();
if(flag)
south[y] = min(south[y], x);
else
north[y] = max(north[y], x);
for(i = 0; i < 4; i++) {
tx = x+dx[i], ty = y+dy[i];
if(tx < 0 || ty < 0 || tx >= R || ty >= C)
continue;
if(used[tx][ty] || g[tx][ty] == '.')
continue;
used[tx][ty] = 1;
X.push(tx), Y.push(ty);
}
}
}
int main() {
int i, j, k;
while(scanf("%d %d %d %d", &R, &C, &B, &S) == 4) {
for(i = 0; i < R; i++)
scanf("%s", &g[i]);
for(i = 0; i < C; i++)
north[i] = -0xfffffff, south[i] = 0xfffffff;
memset(used, 0, sizeof(used));
for(i = 0; i <= B; i++)
supdp[i] = 1000000000;
color(0, 0, 0);
color(R-1, 0, 1);
supdp[0] = 0;
for(i = 0; i < C; i++) {
if(i > S) {
for(j = 1; j <= B; j++)
supdp[j] = min(supdp[j], dp[i-S-1][j]);
}
int cost = south[i]-north[i]-1;
for(j = 1; j <= B; j++) {
dp[i][j] = supdp[j-1]+cost;
}
}
int ret = 0xfffffff;
for(i = 0; i < C; i++)
ret = min(ret, dp[i][B]);
printf("%d\n", ret);
}
return 0;
}
文章定位：
