ACM DP Longest Run on a Snowboard

清疚 2022-06-11 09:37 86阅读 0赞

滴，集训第十八天打卡。

今天开始报名中国大学生程序设计竞赛了...

等我知道的时候我的大腿们都被抱走了...

只能自己瞎划水了...

**UVA 10285 Longest Run on a Snowboard**

**![20170804102950184][]**

**![20170804103001053][]**

**题目大意：n组数据，先输入人名，然后x\*y的滑雪场，滑雪者只能从高的滑到低的地方，且方向只能是上，下，左和右，问滑雪者最长能滑几个单元。**

**思路：这题实际上就是求矩阵上的最长严格连续递减序列，我代码写的有点像深搜+dp的味道...**

#include<iostream>
    #include<string.h>
    using namespace std;
    int map[110][110],vis[110][110],arry[110][110];
    int dir[4][2]={
       {1,0},{-1,0},{0,1},{0,-1}};
    int n,m;
    int dp(int x,int y)
    {
    	int i,dx,dy;
        if(vis[x][y]) return arry[x][y];
        for(i=0;i<4;i++)
        {
            dx=x+dir[i][0];
    		dy=y+dir[i][1];
            if(dx>=0&&dx<n&&dy>=0&&dy<m&&map[dx][dy]<map[x][y])
            arry[x][y]=max(dp(dx,dy)+1,arry[x][y]);
        }
        vis[x][y]=1;
        return arry[x][y];
    }
    int main()
    {
        int num,i,j,cnt,maxn;
        cin>>num;
        while(num--)
        {
            string name;
            cin>>name>>n>>m;
            memset(map, 0, sizeof(map));
            memset(vis, 0, sizeof(vis));
            for(i=0;i<n;i++)
            {
                for(j=0;j<m;j++)
                {
                    cin>>map[i][j];
                    arry[i][j]=0;
                }
            }
            maxn=0;
            for(i=0;i<n;i++)
            {
                for(j=0;j<m;j++)
                    {
                        cnt=dp(i,j);
                        if(cnt>maxn) 
    					maxn=cnt;
                    }
            }
            cout<<name<<": "<<maxn+1<<endl;
        }
        return 0;
    }

[20170804102950184]: /images/20220611/0e61f53621e3461fb273f8b5703d7af0.png
[20170804103001053]: /images/20220611/af86759106574149a467b7f859d31258.png