Posts Tagged 记忆化搜索

记忆化搜索

Posted by twcai in ACM/ICPC on April 5, 2009

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

  1. //TOJ 3234
  2. #include <iostream>
  3. #include <queue>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. int n, ret;
  8. int d[101][101];
  9. int dp[101][101];
  10.  
  11. inline int dfs(int x, int y)
  12. {
  13.     //printf("%d %d\n", x, y);
  14.     if(x == 0 && y == 3){
  15.         x = 0, y = 3;
  16.     }
  17.     if(dp[x][y] > 0)
  18.         return dp[x][y];
  19.     int i, op;
  20.     op = x -1;
  21.     for(i = 0; op >= 0 && i < n; i++){
  22.         if(abs(i - y) > 1 && d[op][i] > d[x][y] )
  23.             dp[x][y] = max(dp[x][y], dfs(op, i) +1);
  24.     }
  25.     op = x +1;
  26.     for(i = 0; op < n && i < n; i++){
  27.         if(abs(i - y) > 1 && d[op][i] > d[x][y] )
  28.             dp[x][y] = max(dp[x][y], dfs(op, i) +1);
  29.     }
  30.     op = y -1;
  31.     for(i = 0; op >= 0 && i < n; i++){
  32.         if(abs(i - x) > 1 && d[i][op] > d[x][y] )
  33.             dp[x][y] = max(dp[x][y], dfs(i, op) +1);
  34.     }
  35.     op = y +1;
  36.     for(i = 0; op < n && i < n; i++){
  37.         if(abs(i - x) > 1 && d[i][op] > d[x][y] )
  38.             dp[x][y] = max(dp[x][y], dfs(i, op) +1);
  39.     }
  40.     if(dp[x][y] < 0)
  41.         dp[x][y] = 1;
  42.     return dp[x][y];
  43. }
  44.  
  45. int main()
  46. {
  47.     int x, y;
  48.     int i, j;
  49.     //freopen("ACM.out", "w", stdout);
  50.  
  51.     while(scanf("%d", &n) != EOF){
  52.         scanf("%d %d", &x, &y);
  53.         for(i = 0; i < n; i++){
  54.             for(j = 0; j < n; j++){
  55.                 scanf("%d", &d[i][j]);
  56.             }
  57.         }
  58.         memset(dp, -1, sizeof(dp));
  59.         ret = dfs(x -1, y -1);
  60.         printf("%d\n", ret);
  61.     }
  62.     return 0;
  63. }

Read the rest of this entry »

, ,

No Comments