2011-08-16 21:20:00Morris
d522. 走棋盘
內容 ：
有一个n*n的棋盘，每个方格里都有着相应的数字。你从左上角出发，每次可以向上下左右四个方向最多移动k格，并且要求你每次到达的方格里的数字必须大于上一次所在方格的数字。现在要求你走过的方格的所有数之和最大，问这个最大和是多少。
輸入說明
：
输入数据首先为两个正整数n、k（1<=n<=100,0<=k<=n） 不换行。
接下来的n行(包括n,k这一行)，每行有n个integer范围的整数，表示地图中的数。
輸出說明
：
输出数据只有一行，为最大的和。
範例輸入 ：
2 2 2 3 4 5
範例輸出 ：
11
提示
：
样例解释:
本应为
2 2
2 3
4 5
但实际上n,k后并未换行,就成了
2 2 2 3
4 5
出處
：
动起来
(管理：scientific)
作法 : DP
重要的是, 我不懂題目的 k 的限定, 後來發現, 他是一次移動的時候, 可以走 k,
也就是中間可以跨越,
那 DP就是先將數字排序過後一次, 從最小的開始更新
作法 : DP
重要的是, 我不懂題目的 k 的限定, 後來發現, 他是一次移動的時候, 可以走 k,
也就是中間可以跨越,
那 DP就是先將數字排序過後一次, 從最小的開始更新
/**********************************************************************************/
/* Problem: d522 "走棋盘" from 动起来 */
/* Language: C */
/* Result: AC (6ms, 523KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-16 20:24:06 */
/**********************************************************************************/
#include<stdio.h>
struct Link {
int x, y;
long long v;
}Data[10001], X[10001];
void Merge(int l, int m, int h) {
int In1 = l, In2 = m+1;
int a, b, Top = 0;
while(In1 <= m && In2 <= h) {
if(Data[In1].v < Data[In2].v)
X[Top++] = Data[In1++];
else
X[Top++] = Data[In2++];
}
while(In1 <= m) X[Top++] = Data[In1++];
while(In2 <= h) X[Top++] = Data[In2++];
for(a = 0, b = l; a < Top; a++, b++)
Data[b] = X[a];
}
void MergeSort(int l, int h) {
if(l < h) {
int m = (l+h)/2;
MergeSort(l, m);
MergeSort(m+1, h);
Merge(l, m, h);
}
}
long long DP[101][101], MinV = -2147483647;
main() {
MinV = MinV;
int n, k, a, b, c, d;
long long map[101][101];
int D[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
while(scanf("%d %d", &n, &k) == 2) {
for(a = 0, c = 0; a < n; a++)
for(b = 0; b < n; b++) {
scanf("%lld", &map[a][b]);
Data[c].x = a, Data[c].y = b, Data[c++].v = map[a][b];
DP[a][b] = MinV;
}
MergeSort(0, n*n-1);
DP[0][0] = map[0][0];
int x, y, tx, ty, d;
long long v, tv;
long long Ans = map[0][0], tmp;
for(a = 0; a < n*n; a++) {
for(b = 0; b < 4; b++) {
x = Data[a].x, y = Data[a].y, v = map[x][y];
for(c = 1; c <= k; c++) {
tx = x+D[b][0]*c, ty = y+D[b][1]*c;
if(tx >= 0 && tx < n && ty >= 0 && ty < n && v < map[tx][ty]) {
tv = map[tx][ty];
if(DP[x][y] == MinV) continue;
tmp = DP[x][y] + tv;
if(DP[tx][ty] < tmp) {
DP[tx][ty] = tmp;
Ans = Ans > tmp ? Ans : tmp;
}
}
}
}
}
printf("%lld\n", Ans);
}
return 0;
}
上一篇：a209. 街友的寒冷夜晚
下一篇：a160. 變態想要下棋!!!