#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
struct num
{
long num,x,y;
long w,s,a,d;
}dot[250001l];
long dp[250001l];
long b[250001l];
void csort(long n)
{
long c[50001l];
long i;
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
for(i=1;i<=n;i++)
c[dot[i].num]++;
for(i=2;i<=50000;i++)
c[i]+=c[i-1];
for(i=1;i<=n;i++)
{
b[c[dot[i].num]]=i;
c[dot[i].num]--;
}
}
int main(int argc, char *argv[])
{
long r,c,i,j;
long n,mm=0;
memset(dot,0,sizeof(dot));
n=1;
scanf("%d%d",&r,&c);
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
{
scanf("%d",&dot[n].num);
dot[n].x=i;
dot[n].y=j;
if(i-1>=1)
dot[n].w=n-c;else dot[n].w=-1;
if(i+1<=r)
dot[n].s=n+c;else dot[n].s=-1;
if(j-1>=1)
dot[n].a=n-1;else dot[n].a=-1;
if(j+1<=c)
dot[n].d=n+1;else dot[n].d=-1;
n++;
}
n-=1;
csort(n);
memset(dp,0,sizeof(dp));
/* for(i=1;i<=n;i++)
{
cout<<i<<' '<<dot[i].num<<'x'<<dot[i].x<<'y'<<dot[i].y<<'w';
cout<<dot[i].w<<'s'<<dot[i].s<<'a'<<dot[i].a<<'d'<<dot[i].d<<endl;
}*/
for(i=n;i>=1;i--)
{
if(dot[b[i]].w!=-1)if(dp[dot[b[i]].w]<dp[b[i]]+1&&dot[dot[b[i]].w].num<dot[b[i]].num)dp[dot[b[i]].w]=dp[b[i]]+1;
if(dp[dot[b[i]].w]>mm)mm=dp[dot[b[i]].w];
if(dot[b[i]].s!=-1)if(dp[dot[b[i]].s]<dp[b[i]]+1&&dot[dot[b[i]].s].num<dot[b[i]].num)dp[dot[b[i]].s]=dp[b[i]]+1;
if(dp[dot[b[i]].s]>mm)mm=dp[dot[b[i]].s];
if(dot[b[i]].a!=-1)if(dp[dot[b[i]].a]<dp[b[i]]+1&&dot[dot[b[i]].a].num<dot[b[i]].num)dp[dot[b[i]].a]=dp[b[i]]+1;
if(dp[dot[b[i]].a]>mm)mm=dp[dot[b[i]].a];
if(dot[b[i]].d!=-1)if(dp[dot[b[i]].d]<dp[b[i]]+1&&dot[dot[b[i]].d].num<dot[b[i]].num)dp[dot[b[i]].d]=dp[b[i]]+1;
if(dp[dot[b[i]].d]>mm)mm=dp[dot[b[i]].d];
if(dp[b[i]]>mm)mm=dp[b[i]];
}
printf("%d\n",mm+1);
system("pause");
return 0;
}
vijos_dp_5problems.rar_vijos
版权申诉
179 浏览量
2022-09-24
14:06:27
上传
评论
收藏 3KB RAR 举报
weixin_42651887
- 粉丝: 75
- 资源: 1万+
最新资源
- MyBatis动态SQL是一种强大的特性,它允许我们在SQL语句中根据条件动态地添加或删除某些部分,从而实现更加灵活和高效的数据
- MyBatis动态SQL是一种强大的特性,它允许我们在SQL语句中根据条件动态地添加或删除某些部分,从而实现更加灵活和高效的数据
- 【ERP标准流程-标准流程-进货管理】(DOC 17页).doc
- MyBatis动态SQL是一种强大的特性,它允许我们在SQL语句中根据条件动态地添加或删除某些部分,从而实现更加灵活和高效的数据
- MyBatis动态SQL是一种强大的特性,它允许我们在SQL语句中根据条件动态地添加或删除某些部分,从而实现更加灵活和高效的数据
- Java爬虫项目【项目开发计划】(共12页).docx
- 11111111111
- MyBatis动态SQL是一种强大的特性,它允许我们在SQL语句中根据条件动态地添加或删除某些部分,从而实现更加灵活和高效的数据
- MyBatis动态SQL是一种强大的特性,它允许我们在SQL语句中根据条件动态地添加或删除某些部分,从而实现更加灵活和高效的数据
- MyBatis动态SQL是一种强大的特性,它允许我们在SQL语句中根据条件动态地添加或删除某些部分,从而实现更加灵活和高效的数据
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈