求助大佬 测试点1wa 为啥错了？

it_hard_to_name @ 2022-07-21 19:18:29

#include<bits/stdc++.h>
using namespace std;
const int maxsize=110;

struct eage{
    int x,h;
}p[maxsize*maxsize];

int d[3][3];
int n,m,ans;
int f[maxsize*maxsize];

bool cmp(eage x,eage y){
    return x.h>y.h;
}

bool check(int i,int j){
    for(int k=1;k<=2;k++)
        if((p[i].x+d[k][1]==p[j].x||p[i].x+d[k][2]==p[j].x)&&p[i].h<p[j].h)return 1;
        return 0;
}

int dp(){
    int ans=0;
    for(int i=1;i<=n*m;i++){
        f[i]=1;
        for(int j=i-1;j;j--)
            if(check(i,j)){
                f[i]=max(f[i],f[j]+1);
                //cout<<f[i]<<endl;
            }
        ans=max(ans,f[i]);
    }
    return ans;
}

int main(){
    cin>>n>>m;
    d[1][1]=m;
    d[1][2]=-m;
    d[2][1]=1;
    d[2][2]=-1;
    int mn=m*n;
    for(int i=1;i<=mn;i++){
        cin>>p[i].h;
        p[i].x=i;
    }
    sort(p+1,p+1+mn,cmp);
    int ans=dp();
    cout<<ans;
    return 0;
}

by it_hard_to_name @ 2022-07-23 10:47:33

ac了

#include <bits/stdc++.h>
using namespace std;
const int maxsize = 110;

struct eage {
    int x, h;
} p[maxsize * maxsize];

int d[3][3];
int n, m, ans, mn;
int f[maxsize * maxsize];

bool cmp(eage x, eage y) {
    return x.h > y.h;
}

bool check(int i, int j) {
    int t[3][3] = {{0, 0, 0}, {0, -m, m}, {0, -1, 1}};
    bool flag1 = (p[i].x <= m);//第一行
    bool flag2 = (p[i].x % m == 1); //第一列
    bool flag4 = (p[i].x % m == 0);//第m列
    bool flag3 = (p[i].x / m + 1 == n && !flag4 || p[i].x == m * n); //第n行
    if (flag1)
        t[1][1] = 0;
    if (flag2)
        t[2][1] = 0;
    if (flag3)
        t[1][2] = 0;
    if (flag4)
        t[2][2] = 0;
    //printf("%d %d %d %d %d\n", p[i].h, flag1, flag2, flag3, flag4);
    for (int k = 1; k <= 2; k++)
        if ((p[i].x + t[k][1] == p[j].x || p[i].x + t[k][2] == p[j].x) && p[i].h < p[j].h)
            return 1;
    return 0;
}

int dp() {
    int ans = 0;
    for (int i = 1; i <= mn; i++) {
        for (int j = i - 1; j; j--)
            if (check(i, j))
                f[i] = max(f[i], f[j] + 1);
        //cout << "f[" << i << "] = " << f[i] << endl;
        ans = max(ans, f[i]);
    }
    return ans;
}

int main() {
    cin >> n >> m;
    d[1][1] = -m;
    d[1][2] = m;
    d[2][1] = -1;
    d[2][2] = 1;
    mn = m * n;
    for (int i = 1; i <= mn; i++) {
        cin >> p[i].h;
        p[i].x = i;
        f[i] = 1;
    }
    sort(p + 1, p + 1 + mn, cmp);
    int ans = dp();
    cout << ans;
    return 0;
}