| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
计数排序按高度DP,0ms水过我也是醉了#include<cstdio>
int c[10050];
bool e[10050];
int h[110][110],a[110][110];
int x[10050][150],y[10050][150],t,i,j,k,r,u,tx,ty,ans;
int d[4]= {0,0,-1,+1},f[4]= {-1,+1,0,0};
int main()
{
scanf("%d%d",&r,&u);
for(i=1; i<=r; i++)
for(j=1; j<=u; j++)
{
scanf("%d",&t);
h[i][j]=t;
x[t][c[t]]=i;
y[t][c[t]]=j;
c[t]++;
}
for(i=0; i<10001; i++)
{
e[i]=1;
for(j=0; j<c[i]; j++)
{
tx=x[i][j];
ty=y[i][j];
for(k=0; k<4; k++)
if((!(e[h[tx+d[k]][ty+f[k]]]))&&(a[tx+d[k]][ty+f[k]]<=a[tx][ty]))
a[tx+d[k]][ty+f[k]]=a[tx][ty]+1;
}
}
for(i=1; i<=r; i++)
for(j=1; j<=u; j++)
if(a[i][j]>ans)
ans=a[i][j];
printf("%d\n",ans+1);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator