80分DP求助 第一组第二组错了

P1434 [SHOI2002] 滑雪

gosgosgoy @ 2020-09-19 19:49:30

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
    int n;
    int m;
    int h;
};
node t[10005];
int c,r,ans;
bool cmp(node x,node y){
    return x.h<y.h ;
}
int a[105][105];
int dp[105][105];
int main(){

    scanf("%d %d",&c,&r);
    for(register int i=0;i<=c+1;i++)
     for(register int j=0;j<=r+1;j++)
      a[i][j]=-1;
    for(int i=0;i<c;i++)
     for(int j=0;j<r;j++){
        scanf("%d",&a[i+1][j+1]);
        t[i*c+j].h=a[i+1][j+1];
        t[i*c+j].n=i+1;
        t[i*c+j].m=j+1;
     }
     sort(t,t+c*r,cmp);
     int p,q;
    //for(register int i=0;i<c;i++)
    //  for(register int j=0;j<r;j++){
    //  p=t[i*c+j].n;
    //      q=t[i*c+j].m;
    for(register int i=0;i<r*c;i++){
        p=t[i].n;
        q=t[i].m;
        dp[p][q]=1;
          if((a[p+1][q]>-1)&&a[p+1][q]<a[p][q]){
            dp[p][q]=max(dp[p][q],dp[p+1][q]+1);
          }
          if((a[p-1][q]>-1)&&a[p-1][q]<a[p][q]){
            dp[p][q]=max(dp[p][q],dp[p-1][q]+1);
          }
          if((a[p][q+1]>-1)&&a[p][q+1]<a[p][q]){
            dp[p][q]=max(dp[p][q],dp[p][q+1]+1);
          }
          if((a[p][q-1]>-1)&&a[p][q-1]<a[p][q]){
            dp[p][q]=max(dp[p][q],dp[p][q-1]+1);
          }
    //  ans=max(dp[p][q],ans);
      }
    for(int i=1;i<=c;i++)
     for(int j=1;j<=r;j++)
      ans=max(dp[i][j],ans);
      printf("%d\n",ans);
}

by sunxiaohan @ 2020-09-19 19:53:22

搜索不好吗?


by gosgosgoy @ 2020-09-19 20:10:06

@sunxiaohan 正在练DP专题,搜索确实好过这题


by sunxiaohan @ 2020-09-19 20:26:06

这不是道DP好题吧


by sunxiaohan @ 2020-09-19 20:26:21

@gosgosgoy


|