*想歪 [Acwing] 1012. 友好城市

https://www.acwing.com/problem/content/1014/

目錄

• 錯誤思路
• 正解
• code(正解)
• code(error)

錯誤思路

不交叉 那麼肯定是求最大上升子序列

因為左邊能對應右邊 是以需要求4遍LIS(左右從頭開始的LIS 左右從尾開始的LIS) 然後取max

結果WA了 (還沒搞清楚)

正解

我們需要把一個岸的 城市 排個序 之後呢 再對其 友好城市 求一遍LIS

(排序這裡nb)

code(正解)

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3+10;
int f[N],n;
struct node
{
    int  a,b;
}num[N];
bool cmp(node x,node y)
{
    return x.a<y.a;

}

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>num[i].a>>num[i].b;
    sort(num+1,num+1+n,cmp);
    for(int i  =1;i<=n;i++)
    {
        f[i] = 1;
        for(int j=1;j<i;j++)
        if(num[j].b<num[i].b)
        f[i] = max(f[i],f[j]+1);
    }
    int ans = 0 ;
    for(int i =1;i<=n;i++)
    ans = max(ans,f[i]);
    cout<<ans;
}
int main()
{
    solve();
    return 0;
}
           

code(error)

#include <bits/stdc++.h>
using namespace std;
const int N  = 5e3+10;
int f1[N],f2[N],a[N],b[N],f3[N],f4[N],c[N],d[N];
int n;
void solve()
{
    cin>>n;

    for(int i= 1; i<=n; i++)
        scanf("%d%d",&a[i],&b[i]),c[i] = a[i],d[i] = b[i];
    reverse(c+1,c+1+n);
    reverse(d+1,d+1+n);

    for (int i = 1; i <= n; i ++ )
    {
        f1[i] = 1; // 隻有a[i]一個數
        for (int j = 1; j < i; j ++ )
            if (a[j] < a[i])
                f1[i] = max(f1[i], f1[j] + 1);
    }

    for (int i = 1; i <= n; i ++ )
    {
        f2[i] = 1; // 隻有a[i]一個數
        for (int j = 1; j < i; j ++ )
            if (b[j] < b[i])
                f2[i] = max(f2[i], f2[j] + 1);
    }


    for (int i = 1; i <= n; i ++ )
    {
        f3[i] = 1; // 隻有a[i]一個數
        for (int j = 1; j < i; j ++ )
            if (c[j] < c[i])
                f3[i] = max(f3[i], f3[j] + 1);
    }
    for (int i = 1; i <= n; i ++ )
    {
        f4[i] = 1; // 隻有a[i]一個數
        for (int j = 1; j < i; j ++ )
            if (d[j] < d[i])
                f4[i] = max(f4[i], f4[j] + 1);
    }




    int ans = 0 ;
    for(int i= 1; i<=n; i++)
    {
        //ans = max(f2[i],f1[i]);
        ans = max(ans,f2[i]);
        ans = max(ans,f1[i]);
    }

    for(int i =1; i<=n; i++)
    {
        ans = max(ans,f3[i]);
        ans = max(ans,f4[i]);
    }
    cout<<ans<<endl;

}
int main()
{
    solve();
    return 0;
}