Contents
SGU-167 I-country
Time Limit: 750ms
Memory Limit: 64MB
Description
According to top-secret A-country plans, I-country is divided into N*M equal squares, each square contains some oil resources. They want to occupy all the territory of I-country, but the UN (United Nations) will allow them to occupy only K squares. Of course, A-country want to get control over as many oil as possible, but, they will have to guard all their territory. So, they need their territory to be easy-controlled, i.e. from any square to any it must be possible to get moving only along two directions (selected from the next list: left, right, up, down; for different squares pairs of directions may differ).
You are to write a program, which determinies, what squares will be occupyed by A-country. If there are several solutions, you may output any.
Input
On the first line of input there are 3 integer numbers N,M,K (1<=N,M<=15, 0<=K<=N*M). Next N lines contains M integers each, which are the number of oil resource on that square. Each of this numbers lies in range of 0 to 1000.
Output
On the first line of output, write string “Oil : X”, where integer number X — the maximal number of oil which can be controlled by A-country. Next you should output K pairs of numbers — coordinates of the squares which will be occupied by A-country. The first coordinate is number of row (top to bottom, starting from 1), second is number of column (left to right, starting from 1).
Sample Input
2 3 4
10 20 30
40 2 3
Sample Output
Oil : 100
1 1
1 2
1 3
2 1
解题思路
题目要求在一个 $N \times M$ 的矩阵中找到一个包含 $K$ 个格子的凸连通块，使得连通块中格子权值和最大。输出值和具体方案。 $N,M \leq 15, k \leq 225 $
我们发现，一个凸联通块在图形中表现为每一行的左端点坐标先递减，后递增，右端点先递增后递减。
可以考虑使用DP解决本题，参数分别为
– 已经处理的行数
– 已经选出的格子数
– 当前行左端点位置（0为递增,1为递减）
– 当前行右端点位置
– 左端点单调性类型
– 右端点单调性类型
左右端点共有 $ 2 \times 2$种情况，分类讨论
1. 左边界递减，右边界递增
如果 $ j = r-l+1 > 0 $
$$F[i, j, l, r, 1, 0] = \sum_{p=l}^{r} A[i, p] + F[i-1, 0, 0, 0, 1, 0] $$
如果 $ j > r-l+1 > 0 $
$$F[i, j, l, r, 1, 0] = \sum_{p=l}^{r} A[i, p] + \max_{l \leq p \leq q \leq r} { F[i-1, j-(r-l+1), p, q, 1, 0] } $$
2. 左边界递减，右边界递减
$$F[i, j, l, r, 1, 1] = \sum_{p=l}^{r} A[i, p] + \max_{l \leq p \leq r \leq q} { F[i-1, j-(r-l+1), p, q, 1, 0/1] } $$
3. 左边界递增，右边界递增
$$F[i, j, l, r, 0, 0] = \sum_{p=l}^{r} A[i, p] + \max_{p \leq l \leq q \leq r} { F[i-1, j-(r-l+1), p, q, 0/1, 0] } $$
4. 左边界递增，右边界递减
$$F[i, j, l, r, 0, 1] = \sum_{p=l}^{r} A[i, p] + \max_{p \leq l \leq r \leq q} { F[i-1, j-(r-l+1), p, q, 0/1, 0/1] } $$
最后答案就是 $max{F[i, K, l, r, x, y]}$
再用一个数组记录每一个状态的转移（由哪个状态转移到这个状态的），递归输出即可。
本题内存限制较为严格，使用char数组记录转移。
#include
#include
#include
#include
#include
#include
using namespace std;
inline int read(){
int x = 0;
char ch = getchar();
while(ch < '0' || ch > '9')
ch = getchar();
while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}
return x;
}
char last_l[16][226][16][16][2][2];
char last_r[16][226][16][16][2][2];
char last_x[16][226][16][16][2][2];
char last_y[16][226][16][16][2][2];
int start_l, start_r, start_x, start_y;
int data[16][16];
int f[16][226][16][16][2][2];
int n, m, k;
int ans, start;
inline void search(int i, int j, int l, int r, int x, int y){
if(j == 0)
return;
int length = r - l + 1;
search(i-1, j-length, last_l[i][j][l][r][x][y], last_r[i][j][l][r][x][y], last_x[i][j][l][r][x][y], last_y[i][j][l][r][x][y]);
for(register int p=l; p<=r; p++)
printf("%d %d\n", i, p);
}
int main(){
n = read();
m = read();
k = read();
for(register int i=1; i<=n; i++)
for(register int j=1; j<=m; j++)
data[i][j] = read();
for(register int i=1; i<=n; i++){
for(register int j=1; j<=k; j++){
for(register int l=1; l<=m; l++){
for(register int r=l; r<=m; r++){
int length = r-l+1;
int sum = 0;
for(register int k=l; k<=r; k++)
sum += data[i][k];
int maxn = 0;
if(j < length)
continue;
if(j == length)
f[i][j][l][r][1][0] = sum + f[i-1][0][0][0][1][0];
else{
for(register int p=l; p<=r; p++)
for(register int q=p; q<=r; q++)
if(f[i-1][j-length][p][q][1][0] > maxn){
maxn = f[i-1][j-length][p][q][1][0];
last_l[i][j][l][r][1][0] = p;
last_r[i][j][l][r][1][0] = q;
last_x[i][j][l][r][1][0] = 1;
last_y[i][j][l][r][1][0] = 0;
}
f[i][j][l][r][1][0] = sum + maxn;
}
maxn = 0;
for(register int p=l; p<=r; p++)
for(register int q=r; q<=m; q++)
for(register int y=0; y<=1; y++)
if(f[i-1][j-length][p][q][1][y] > maxn){
maxn = f[i-1][j-length][p][q][1][y];
last_l[i][j][l][r][1][1] = p;
last_r[i][j][l][r][1][1] = q;
last_x[i][j][l][r][1][1] = 1;
last_y[i][j][l][r][1][1] = y;
}
f[i][j][l][r][1][1] = sum + maxn;
maxn = 0;
for(register int p=1; p<=l; p++)
for(register int q=l; q<=r; q++)
for(register int x=0; x<=1; x++)
if(f[i-1][j-length][p][q][x][0] > maxn){
maxn = f[i-1][j-length][p][q][x][0];
last_l[i][j][l][r][0][0] = p;
last_r[i][j][l][r][0][0] = q;
last_x[i][j][l][r][0][0] = x;
last_y[i][j][l][r][0][0] = 0;
}
f[i][j][l][r][0][0] = sum + maxn;
maxn = 0;
for(register int p=1; p<=l; p++)
for(register int q=r; q<=m; q++)
for(register int x=0; x<=1; x++)
for(register int y=0; y<=1; y++)
if(f[i-1][j-length][p][q][x][y] > maxn){
maxn = f[i-1][j-length][p][q][x][y];
last_l[i][j][l][r][0][1] = p;
last_r[i][j][l][r][0][1] = q;
last_x[i][j][l][r][0][1] = x;
last_y[i][j][l][r][0][1] = y;
}
f[i][j][l][r][0][1] = sum + maxn;
}
}
}
}
for(register int i=1; i<=n; i++){
for(register int l=1; l<=m; l++){
for(register int r=l; r<=m; r++){
for(register int x=0; x<=1; x++){
for(register int y=0; y<=1; y++){
if(f[i][k][l][r][x][y] > ans){
ans = f[i][k][l][r][x][y];
start_l = l;
start_r = r;
start_x = x;
start_y = y;
start = i;
}
}
}
}
}
}
printf("Oil : %d\n", ans);
search(start, k, start_l, start_r, start_x, start_y);
return 0;
}