uva 10285——Longest Run on a Snowboard

题意：在一个R*c的矩阵上找一条高度严格递减的最长路，起点任意，每次可以走上下左右。

思路：DAG上的最长路问题，直接套用记忆化搜索的模板，dp（i，j）=max（dp（ii，jj）四个方向最大值），然后找出来最大的即可。

code：

#include <bits/stdc++.h> using namespace std;using namespace std;typedef long long ll; typedef unsigned long long ull; typedef long double ld;const int N=1000000; const int M=105; const int mod=1000000007; const double pi=acos(-1.0);#define cls(x,c) memset(x,c,sizeof(x)) #define ft(i,s,t) for (int i=s;i<=t;i++)int w,h; int mp[M][M],dp[M][M]; char s[M]; int tx[]={1,-1,0,0}; int ty[]={0,0,1,-1}; bool ok(int i,int j) {return (i>=0&&i<w&&j>=0&&j<h); } int sol(int i,int j) {int f=0;int& ans=dp[i][j];if (ans!=-1) return ans;ans=-1;for (int p=0;p<4;p++){int x=i+tx[p],y=j+ty[p];if (mp[x][y]<mp[i][j]&&ok(x,y)){ans=max(ans,sol(x,y)+1);f=1;}}if (!f) ans=1;return ans; } int main() {int T;scanf("%d",&T);while (T--){scanf("%s %d %d",s,&w,&h);ft(i,0,w-1) ft(j,0,h-1) scanf("%d",&mp[i][j]);cls(dp,-1); int ans=-1;ft(i,0,w-1) ft(j,0,h-1) ans=max(ans,sol(i,j));printf("%s: %d\n",s,ans);} }

总结

以上是生活随笔为你收集整理的uva 10285——Longest Run on a Snowboard的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。