DP求助

P1434 [SHOI2002] 滑雪

BlachSnake @ 2021-04-20 20:13:29

#include<algorithm>
#include<stdio.h>
#include<ctype.h>
#define max(x,y) (x<y?x:y)
namespace io{
    int Read(){
        int x=0;
        bool d=0;
        char c=getchar();
        for(;!isdigit(c);c=getchar())if(c=='-')d=1;
        for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+c-48;
        if(d)x=-x;
        return x;
    }
    void Print(int x){
        if(x<0)x=-x,putchar('-');
        int a[12],l=0;
        for(;x;x/=10)a[l++]=x%10;
        if(!l)putchar('0');
        for(l--;~l;l--)putchar(a[l]+48);
        putchar(' ');
    }
}
using namespace io;
using std::sort;
const int N=128,mx[4]={1,0,-1,0},my[4]={0,1,0,-1};
struct node{int x,y,v;}t[N*N];
int a[N][N],f[N][N];
inline bool cmp(node a,node b){return a.v<b.v;}
int main(){
    int r=Read(),c=Read(),m=r*c,x,y,s=0;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            a[i][j]=Read(),t[++s]=(node){i,j,a[i][j]};
    sort(t+1,t+m+1,cmp);
    s=0;
    for(int i=1;i<=m;i++){
        x=t[i].x,y=t[i].y;
        for(int j=0;j<4;j++)
            if(a[x+mx[j]][y+my[j]]<a[x][y])
                f[x][y]=max(f[x][y],f[x+mx[i]][y+my[i]]);
        f[x][y]++;
        s=max(s,f[x][y]);
    }
    Print(s);
    return 0;
}

RT,不知道sort的时候出什么问题了,总是RE……

所以那个WA是什么意思

求调QwQ


by BlachSnake @ 2021-04-20 20:17:56

艹,f[x+mx[i][y+my[i]]是smg……

还有(x<y?x:y)又是smg……

已AC,此帖终结


by qqqqq111 @ 2021-04-20 20:35:21

dp这么难的吗连你也。。。


by qqqqq111 @ 2021-04-20 20:47:50

快删吧


by BlachSnake @ 2021-04-21 19:15:01

@qqqqq111 记搜=DP

但DP!=记搜


by qqqqq111 @ 2021-04-21 22:34:35


by tomato1 @ 2021-04-24 11:14:22

DP???


|