台湾菜

记忆化搜索

twcai • acm/icpc

居然整ACM那么久记忆化搜索还不会,今晚TOJ的C就这么卡在那边了……
不过还好学起来还是蛮简单了,回到寝室后A了比较相似的两题,一题是TOJ 3234,一题是POJ 1088.
我的做法都是用dfs扩展结点,用一个数组保存最优解。
贴下代码(顺便一提,今天看到一个等宽字体叫Monaco,狂好看!在coolcode的css里改了下,但是没效果=,= 郁闷):
//TOJ 3234
#include
#include
#include
using namespace std;

int n, ret;
int d[101][101];
int dp[101][101];

inline int dfs(int x, int y)
{
//printf("%d %d\n", x, y);
if(x == 0 && y == 3){
x = 0, y = 3;
}
if(dp[x][y] > 0)
return dp[x][y];
int i, op;
op = x -1;
for(i = 0; op >= 0 && i < n; i++){
if(abs(i - y) > 1 && d[op][i] > d[x][y] )
dp[x][y] = max(dp[x][y], dfs(op, i) +1);
}
op = x +1;
for(i = 0; op < n && i < n; i++){
if(abs(i - y) > 1 && d[op][i] > d[x][y] )
dp[x][y] = max(dp[x][y], dfs(op, i) +1);
}
op = y -1;
for(i = 0; op >= 0 && i < n; i++){
if(abs(i - x) > 1 && d[i][op] > d[x][y] )
dp[x][y] = max(dp[x][y], dfs(i, op) +1);
}
op = y +1;
for(i = 0; op < n && i < n; i++){
if(abs(i - x) > 1 && d[i][op] > d[x][y] )
dp[x][y] = max(dp[x][y], dfs(i, op) +1);
}
if(dp[x][y] < 0)
dp[x][y] = 1;
return dp[x][y];
}

int main()
{
int x, y;
int i, j;
//freopen("ACM.out", "w", stdout);

while(scanf("%d", &n) != EOF){
scanf("%d %d", &x, &y);
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
scanf("%d", &d[i][j]);
}
}
memset(dp, -1, sizeof(dp));
ret = dfs(x -1, y -1);
printf("%d\n", ret);
}
return 0;
}

//POJ 1088
#include
#include
using namespace std;

int n, m, ret;
int d[102][102], dp[102][102];
int dir[4][2] = {0, 1, -1, 0, 0, -1, 1, 0};

inline int dfs(int x, int y)
{
//printf("%d %d\n", x, y);
if(dp[x][y] > 0)
return dp[x][y];
int i;
int tx, ty;
for(i = 0; i < 4; i++){
tx = x + dir[i][0], ty = y + dir[i][1];
if(tx < 0 || tx >= n || ty < 0 || ty >= m)
continue;
if(d[tx][ty] <= d[x][y])
continue;
dp[x][y] = max(dp[x][y], dfs(tx, ty) +1);
}
if(dp[x][y] < 0)
dp[x][y] = 1;
return dp[x][y];
}

int main()
{
int i, j;
//freopen("ACM.out", "w", stdout);
while(scanf("%d %d", &n, &m) != EOF)
{
for(i = 0; i < n; i++){
for(j = 0; j < m; j++){
scanf("%d", &d[i][j]);
}
}
memset(dp, -1, sizeof(dp));
ret = 0;
for(i = 0; i < n; i++){
for(j = 0; j < m; j++){
ret = max(ret, dfs(i, j));
}
}
printf("%d\n", ret);
}
return 0;
}

comments powered by Disqus