题号:P1434
这道题需要留着细细品味……
这道题也挺恶心，用尽各种优化方法……
需要写一下注释，省得我以后看不懂自己写的代码……
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include<iostream> #include<string> #include<cstring> #include<algorithm> #include<cstdlib> using namespace std; int array[105][105]; int memory[105][105]; bool check[105][105]; struct s{ int x,y,n; bool operator < (s& s2){ return this->n>s2.n; } }ss[11025]; int r,c; int shift_x[5]={0,-1,1,0,0},shift_y[5]={0,0,0,-1,1};//left,right,up,down int safe_array(int x,int y){ if(x>=1&&x<=r&&y>=1&&y<=c)return array[x][y]; else return -1; }//保证数组不越界 int dfs(int x,int y,int last){//dfs是从截止点step为0推到起始点的 if(safe_array(x,y)==-1||last<=array[x][y]||check[x][y])return 0; if(memory[x][y]!=-1)return memory[x][y]; check[x][y]=true; int max_=-1; for(int i=1;i<=4;i++){ int t=dfs(x+shift_x[i],y+shift_y[i],array[x][y]); if(t>max_)max_=t; } check[x][y]=false; return memory[x][y]=max_+1; } int main(){ memset(memory,-1,sizeof(memory)); cin>>r>>c; int ptr=0; for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++){ cin>>array[i][j]; ss[ptr].x=i; ss[ptr].y=j; ss[ptr].n=array[i][j]; ptr++; } } int max_=-1; sort(ss,ss+ptr);//先排序，由坡高到坡低去进行dfs，这样坡低的在刚一开始就会因为记忆化搜索直接return for(int i=0;i<ptr;i++){ int t=dfs(ss[i].x,ss[i].y,ss[i].n+1); if(t>max_)max_=t;//收集最长路径 } cout<<max_; } |
20180730更新：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | #include<iostream> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<queue> #include<map> #include<functional> using namespace std; int r,c; int arr[105][105]; int f[105][105]; struct node{ int x,y; int v; bool operator < (const node& n2){ return v<n2.v; } }narr[10005]; int narrptr=0; int main() { ios::sync_with_stdio(false); memset(arr,0x7f,sizeof(arr)); cin>>r>>c; for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++){ cin>>arr[i][j]; narr[++narrptr].v=arr[i][j]; narr[narrptr].x=i; narr[narrptr].y=j; } } sort(narr+1,narr+r*c+1); for(int i=1;i<=narrptr;i++){ if(narr[i].v>arr[narr[i].x-1][narr[i].y])f[narr[i].x][narr[i].y]=max(f[narr[i].x][narr[i].y],f[narr[i].x-1][narr[i].y]+1); if(narr[i].v>arr[narr[i].x+1][narr[i].y])f[narr[i].x][narr[i].y]=max(f[narr[i].x][narr[i].y],f[narr[i].x+1][narr[i].y]+1); if(narr[i].v>arr[narr[i].x][narr[i].y-1])f[narr[i].x][narr[i].y]=max(f[narr[i].x][narr[i].y],f[narr[i].x][narr[i].y-1]+1); if(narr[i].v>arr[narr[i].x][narr[i].y+1])f[narr[i].x][narr[i].y]=max(f[narr[i].x][narr[i].y],f[narr[i].x][narr[i].y+1]+1); } int mmax=0; for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++){ mmax=max(mmax,f[i][j]); } } cout<<mmax+1; } |