0分求调

B3637 最长上升子序列

YYPanda233 @ 2024-08-15 23:22:49

subtask#1 AC subtask#0 前两个点WA，后三个点TLE

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 5005

ll n, a[MAXN], ans;

ll dfs(int index, int maxnum)
{
    if (index >= n) return maxnum;

    //cout << index << " " << a[index] << " " << maxnum << "\n";
    if (a[index] <= maxnum) return dfs(index + 1, 0);
    else return max(dfs(index + 1, 0), dfs(index + 1, a[index]));
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (ll i = 0 ; i < n ; i++) cin >> a[i];
    ans = dfs(0, 0);
    cout << ans;
    return 0;
}

求佬调一下:(

by haimingbei @ 2024-08-15 23:31:15

@YYPanda233 我可以说这是dp吗。。。

/*
B3637 最长上升子序列
*/
#include<bits/stdc++.h>
using namespace std;
int a[5005],dp[5005];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        dp[i]=1;
        for(int j=1;j<i;j++){
            if(a[j]<a[i]){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    sort(dp+1,dp+n+1);
    cout<<dp[n];
    return 0;
}

by YYPanda233 @ 2024-08-15 23:47:35

@haimingbei 应该是吧（

能AC的算法都是好算法

但是我想要这种dfs的代码，本liruo看不懂，从昨天下午才开始学

谢谢大佬回答;)

|