有什么问题

P2766 最长不下降子序列问题

OneRepublic @ 2018-11-03 08:52:19

#include<bits/stdc++.h>
using namespace std;
int p[10000],a[10000];
struct ss
{
    int x,y;
}
dp[10000];
char s[100000];
int main()
{
    int n,i,j,k,l=0,key;
    while(gets(s));
    key=strlen(s);
    s[key]=' ';
    int t=0;
    for(i=0,j=0;i<=key;i++)
    {
        if(s[i]!=' ') t=t*10+s[i]-'0';
        else
        {
            p[j++]=t; t=0;
        }
    }
    n=j;
    memset(dp,0,sizeof(dp));
    memset(a,0,sizeof(a));
    int sum=-1;
    for(i=1;i<n;i++)
    {
        for(j=0;j<i;j++)
        {
            if(p[j]<p[i]&&dp[j].x+1>dp[i].x)
            {
                dp[i].x=dp[j].x+1;
                dp[i].y=j;
            }
        }
        if(dp[i].x>sum)
        {
            sum=dp[i].x;
            k=i;
        }
    }
    a[sum]=p[k];
    int m=dp[k].y;
    for(i=sum-1;i>=0;i--)
    {
        a[i]=p[m];
        m=dp[m].y;
    }
    cout<<"max="<<++sum<<endl;
    for(i=0;i<sum;i++)
    {
        cout<<a[i]<<" ";
    }
    return 0;
}

大佬看一看(本人是oier中的萌新


|