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.zzzyk.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; 
} 

补充：软件开发 , C++ ,

上一个：Command 模式C++ 代码
下一个：c++ 模板