HDOJ 2571 命運

動態規劃加搜索，wrong了一次，我們知道每次移動的方向，進行搜索選取最大值即可，不需要另外的數組保存結果，加一個訪問數組visit，原來訪問已經得到最大值，只要訪問過了就直接可以返回最大值。

代碼：

[cpp] 
#include<iostream> 
const int INF=-100000000; 
using namespace std; 
int map[22][1002]; 
bool visit[22][1002]; 
int n,m; 
int DFS(int i,int j) 
{ 
    if( visit[i][j]||i==n&&j==m) 
        return map[i][j]; 
    int mx=INF; 
    if(i+1<=n)    mx=max(mx,DFS(i+1,j)); 
    if(j+1<=m)    mx=max(mx,DFS(i,j+1)); 
    for(int k=2; k*j<=m; k++) 
            mx=max(mx,DFS(i,k*j)); 
    map[i][j]+=mx;  //用map保存結果即可。 
    visit[i][j]=true; 
    return map[i][j]; 
}  www.2cto.com
int main() 
{ 
    int c,i,j; 
    scanf("%d",&c); 
    while( c--){ 
           scanf("%d%d",&n,&m); 
           memset(map,0,sizeof(map)); 
           memset(visit,0,sizeof(visit)); 
           for( i=1; i<=n; i++) 
                for( j=1; j<=m; j++)     
                     scanf("%d",&map[i][j]); 
          printf("%d\n",DFS(1,1)); 
    } 
    return 0; 
}