打电话沟通做网站话术,关于网站优化的文章,个人作品展示网站模板,个人买卖网站如何做Problem F: 动态规划进阶题目之滑雪 Time Limit: 1 Sec Memory Limit: 64 MBSubmit: 4 Solved: 3[Submit][Status][Web Board]Description Michael喜欢滑雪百这并不奇怪#xff0c; 因为滑雪的确很刺激。可是为了获得速度#xff0c;滑的区域必须向下倾斜#xff0c;而且当… Problem F: 动态规划进阶题目之滑雪 Time Limit: 1 Sec Memory Limit: 64 MB Submit: 4 Solved: 3 [Submit][Status][Web Board]Description Michael喜欢滑雪百这并不奇怪 因为滑雪的确很刺激。可是为了获得速度滑的区域必须向下倾斜而且当你滑到坡底你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一当且仅当高度减小。在上面的例子中一条可滑行的滑坡为24-17-16-1。
当然25-24-23-...-3-2-1更长。事实上这是最长的一条。 Input 输入的第一行表示区域的行数R和列数C(1 R,C 100)。下面是R行每行有C个整数代表高度h0h10000。 Output 输出最长区域的长度。 Sample Input
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9 Sample Output
25 这个题让我很是纠结虽然思路简单但是实现起来挺麻烦的。 这是我在慕课网上看到的两种思路。可能是我脑子笨一直没法实现参考几个代码之后才最终实现代码如下递归型这种比较简单但可能会超时#includecstdio
#includecstring
#includecstdlib
#includeiostream
#includealgorithm
#includecmath
using namespace std;
int h[100][100];
int maxl;
void dfs(int i,int j,int s,int x,int y){if(ixjyh[i][j]!0){if(h[i1][j]h[i][j])dfs(i1,j,s1,x,y);if(h[i][j1]h[i][j])dfs(i,j1,s1,x,y);if(h[i-1][j]h[i][j])dfs(i-1,j,s1,x,y);if(h[i][j-1]h[i][j])dfs(i,j-1,s1,x,y);maxlmax(s,maxl);}}int main()
{int x,y;cinxy;for(int i0;ix;i)for(int j0;jy;j)cinh[i][j];maxl0;for(int i0;ix;i)for(int j0;jy;j)dfs(i,j,1,x,y);coutmaxl;}人人为我递推型#includecstdio
#includecstring
#includecstdlib
#includeiostream
#includealgorithm
#includecmath
using namespace std;
int d[110][110],dp[110][110];
struct node{int x,y,h;
}a[10010];
int cmp(node a,node b)//按高度排序
{return a.hb.h;
}
int main()
{int x,y,k0,maxl;cinxy;for(int i0;ix;i)for(int j0;jy;j){cind[i][j];dp[i][j]1;a[k].xi;a[k].yj;a[k].hd[i][j];k;}sort(a,ak,cmp);maxl0;for(int i0;ik;i){if(d[a[i].x][a[i].y]d[a[i].x1][a[i].y])dp[a[i].x][a[i].y]max(dp[a[i].x][a[i].y],dp[a[i].x1][a[i].y]1);if(d[a[i].x][a[i].y]d[a[i].x-1][a[i].y])dp[a[i].x][a[i].y]max(dp[a[i].x][a[i].y],dp[a[i].x-1][a[i].y]1);if(d[a[i].x][a[i].y]d[a[i].x][a[i].y1])dp[a[i].x][a[i].y]max(dp[a[i].x][a[i].y],dp[a[i].x][a[i].y1]1);if(d[a[i].x][a[i].y]d[a[i].x][a[i].y-1])dp[a[i].x][a[i].y]max(dp[a[i].x][a[i].y],dp[a[i].x][a[i].y-1]1);maxlmax(maxl,dp[a[i].x][a[i].y]);}coutmaxl;
}
