#include <bits/stdc++.h>
using namespace std;
int arr[25],dp[25][2];
int main(){
    ios::sync_with_stdio(false);
    int n=0,ans=0,cnt=0;
    string s;
    cin>>s;
    s+=',';
    int x=0;
    for(int i=0;i<s.size();i++){
        if(s[i]!=',')x=x*10+s[i]-'0';
        else arr[++n]=x,x=0;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++)
            if(arr[i]<=arr[j]&&dp[j][0]>dp[i][0])dp[i][0]=dp[j][0];
            else if(arr[i]>arr[j])dp[i][1]=dp[j][1];
        dp[i][0]++;
        dp[i][1]++;
        ans=max(ans,dp[i][0]);
        cnt=max(cnt,dp[i][1]);
    }
    cout<<ans<<","<<cnt-1;
    return 0;
}

就错一个点

2 条评论

  • @ 2024-08-03 20:34:43
    #include <bits/stdc++.h>
    using namespace std;
    int arr[25],dp[25][2];
    int main()
    {
        ios::sync_with_stdio(false);
        int n=0,ans=0,cnt=0;
        string s;
        cin>>s;
        s+=',';
        int x=0;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]!=',')
                x=x*10+s[i]-'0';
            else 
                arr[++n]=x,x=0;
        }
        for(int i=1;i<=n;i++)
                dp[i][1]=1,dp[i][0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<i;j++)
            {
                if(arr[i]<=arr[j])
                    dp[i][0]=max(dp[i][0],dp[j][0]+1);
                if(arr[i]>arr[j])
                    dp[i][1]=max(dp[j][1]+1,dp[i][1]);//大哥不是每次i+1,dp[i][0],dp[i][j]都同时加一
            }
            ans=max(ans,dp[i][0]);
            cnt=max(cnt,dp[i][1]);
        }
        cout<<ans<<","<<cnt-1;
        return 0;
    }
    
  • @ 2024-08-03 15:09:52

    人机

  • 1

信息

ID
1365
难度
7
分类
动态规划 | 单调性DP 点击显示
标签
递交数
122
已通过
20
通过率
16%
上传者