Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
我的递归解法,是超时的.高手指点一点算法的优化#include<iostream.h> int r,c; void count(int i,int j,int &result,int total,int **p,bool ** flag) { int m=p[i][j]; //比周围的小或周围是边界 if(((total+m)>=result)&&(i+1>=r||p[i+1][j]>m)&&(i-1<0||p[i-1][j]>m)&&(j-1<0||p[i][j-1]>m)&&(j+1>=c||p[i][j+1]>m)) { total+=m; result=total; return; } //上下左右搜索 if(i+1<r&&p[i+1][j]<m&&!flag[i+1][j]) { flag[i+1][j]=true; count(i+1,j,result,total+m-p[i+1][j],p,flag); flag[i+1][j]=false; } if(i-1>=0&&p[i-1][j]<m&&!flag[i-1][j]) { flag[i-1][j]=true; count(i-1,j,result,total+m-p[i-1][j],p,flag); flag[i-1][j]=false; } if(j+1<c&&p[i][j+1]<m&&!flag[i][j+1]) { flag[i][j+1]=true; count(i,j+1,result,total+m-p[i][j+1],p,flag); flag[i][j+1]=false; } if(j-1>=0&&p[i][j-1]<m&&!flag[i][j-1]) { flag[i][j-1]=true; count(i,j-1,result,total+m-p[i][j-1],p,flag); flag[i][j-1]=false; } } int main() { int i,j,m,n; int result=0,temp=0; cin>>r>>c; int **p=new int *[r]; bool **flag=new bool *[r]; for(i=0;i<r;i++) { flag[i]=new bool [c]; p[i]=new int [c]; for(j=0;j<c;j++) cin>>p[i][j]; } for(i=0;i<r;i++) { for(j=0;j<c;j++) { temp=0; for(m=0;m<r;m++) for(n=0;n<c;n++) { flag[m][n]=false; } flag[i][j]=true; count(i,j,temp,0,p,flag); if(temp>result) result=temp; } } cout<<result<<endl; return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator