题解

203 条题解

  • 2
    @ 2016-10-09 00:41:12

    最后一条数据,一个导弹,所以逆推的童鞋要特判啊。。。。
    动态规划+贪心
    注意输入,建议输入字符串然后做字符串处理
    #include <iostream>
    #include <vector>
    #include <algorithm>

    using namespace std;

    int main()
    {
    int i,j;
    int len;
    string s;
    vector <int> pdd;//序列
    vector <int> f1;//序列长度
    vector <int> sys;//导弹系统当前拦截最高高度
    int n,temp=0,maxl=0;
    cin>>s;
    len=s.size();
    for(i=0;i<len;++i)
    {
    if(s[i]!=',')
    {
    maxl*=10;
    maxl+=(int)s[i]-48;
    }else
    {
    pdd.push_back(maxl);
    maxl=0;
    }
    }
    pdd.push_back(maxl);
    //输入。。。。
    maxl=-1;
    n=pdd.size();
    if(n==1){cout<<1<<','<<0;return 0;}//特判,只有一颗导弹。。。。。
    f1.resize(n);
    for(i=0;i<n;++i)
    f1[i]=1;
    //初始化长度
    for(i=n-2;i>=0;--i)
    {
    temp=f1[i];
    for(j=n-1;j>i;--j)
    if(pdd[i]>=pdd[j]&&temp<f1[i]+f1[j])
    temp=f1[i]+f1[j];
    f1[i]=temp;
    maxl=temp>maxl? temp:maxl;
    }
    //最长不下降子序列
    sys.push_back(pdd[0]);
    for(i=1;i<n;++i)
    {
    len=sys.size();
    sort(sys.begin(),sys.end());
    for(j=0;j<len;++j)
    {
    if(sys[j]>=pdd[i])
    {
    sys[j]=pdd[i];
    break;
    }
    }
    if(j==len)sys.push_back(pdd[i]);
    }
    //贪心
    cout<<maxl<<','<<sys.size()-1;
    //输出
    return 0;
    }

  • 1
    @ 2020-09-13 15:59:11

    懂的都懂 可以运用dilworth定理

    #include<bits/stdc++.h>
    using namespace std;
    int a[1001];
    int n,max1,max2;
    int dp[1001],dpp[1001];
    int main()
    {
        while(scanf("%d",&a[++n])!=EOF)
        {
            getchar();
        };
        n--;
        //cout<<n;
        for(int i=1;i<=n;i++)dp[i]=dpp[i]=1;
        for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
        {
            if(a[j]>=a[i]) dp[i]=max(dp[i],dp[j]+1);
            if(a[j]<a[i]) dpp[i]=max(dpp[i],dpp[j]+1);
        }
        for(int i=1;i<=n;i++)
        {
            max1=max(max1,dp[i]);
            max2=max(max2,dpp[i]);
        }
        cout<<max1<<","<<max2-1;
    } 
    
  • 1
    @ 2018-03-19 21:09:17

    坏掉了坏掉了,最长上升都写错了233333
    第一问:最长不上升;
    第二问:最长严格上升 - 1(已有的一条)

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    int missile[25], n, f[25], pre[25], tmp, cnt, last;
    bool flag, vis[25];
    
    inline int read(){
        if (flag) return 0;
        char ch = getchar();
        int x = 0;
        while (ch < '0' || ch > '9') ch = getchar();
        while (ch >= '0' && ch <= '9'){x *= 10; x += ch - '0'; ch = getchar();}
        if (ch == '\n') flag = true;
        return x;
    }
    
    inline void process(){
        for (int i = last; i != 0; i = pre[i]) {
            vis[i] = true;
        }
    }
    
    inline int lds(bool param){
        int ans = -1;
        for (int i = 1; i <= n; i++) f[i] = 1;
        for (int i = 1; i <= n; i++){
            for (int j = i - 1; j >= 1; j--){
                if ((param ? missile[i] <= missile[j] : missile[i] > missile[j])) f[i] = max(f[i], f[j] + 1);
            }
            ans = max(ans, f[i]);
        }
        return ans;
    }
    
    int main(){
        while (missile[++n] = read()); n--;
        cout << lds(true) << "," << lds(false) - 1 << endl;
      //for (int i = 1; i <= n; i++) cout << f[i] << endl;
        return 0;
    }
    
    
    
  • 1
    @ 2017-10-03 19:46:07

    #include<cstdio>
    #include<cstring>
    int a[1010],f[1010],b[1010],n,max,k;
    int main()
    {
    while(scanf("%d",&k)!=EOF)
    {
    f[++n]=k;
    getchar();
    }
    for(int i=1;i<=n;i++)
    {
    k=0;
    for(int j=i;j>=0;j--)
    if( ( f[i]<=f[j] ) && ( k<a[j] ) ) k=a[j];
    a[i]=k+1;
    if(a[i]>max) max=a[i];
    }
    printf("%d,",max);
    memset(b,0,sizeof(b)); max=0;
    for(int i=1;i<=n;i++)
    {
    k=0;
    for(int j=1;j<=i;j++)
    if( ( f[i]>f[j] ) && ( k<b[j] ) ) k=b[j];
    b[i]=k+1;
    if(b[i]>max) max=b[i];
    }
    printf("%d",max-1);
    return 0;
    }

  • 1
    @ 2017-10-03 19:36:28

    #include<cstdio>
    #include<string.h>
    #include<iostream>
    using namespace std;
    const int maxn=100005;
    int a[maxn];
    int f[maxn];
    int main()//二分神速
    {
    int n=0;
    int l,r,mid;
    while(scanf("%d",&a[++n])!=EOF)
    {
    char k;
    scanf("%c",&k);
    continue;
    }
    n--;
    f[0]=21000000;
    int ans1=0;
    for(int i=1;i<=n;i++)
    {
    if(f[ans1]>=a[i])
    {
    f[ans1+1]=a[i];
    ans1++;
    }
    else
    {
    l=0;r=ans1;
    while(l<r)
    {
    mid=(l+r)/2;
    if(f[mid]>=a[i])l=mid+1;
    else r=mid;
    }
    if(l!=0) f[l]=a[i];
    }
    }
    cout<<ans1<<',';
    memset(f,-1,sizeof(f));
    int ans2=0;
    for(int i=1;i<=n;i++)
    {
    if(f[ans2]<a[i])
    {
    f[ans2+1]=a[i];
    ans2++;
    }
    else
    {
    l=0;r=ans2;
    while(l<r)
    {
    mid=(l+r)/2;
    if(f[mid]>=a[i])r=mid;
    else
    {
    l=mid+1;

    }
    }
    f[l]=a[i];
    }
    }
    cout<<ans2-1<<endl;
    }

  • 0
    @ 2017-10-03 19:45:37

    #include<cstdio>
    #include<cstring>
    int a[1010],f[1010],b[1010],n,max,k;
    int main()
    {
    while(scanf("%d",&k)!=EOF)
    {
    f[++n]=k;
    getchar();
    }
    for(int i=1;i<=n;i++)
    {
    k=0;
    for(int j=i;j>=0;j--)
    if( ( f[i]<=f[j] ) && ( k<a[j] ) ) k=a[j];
    a[i]=k+1;
    if(a[i]>max) max=a[i];
    }
    printf("%d,",max);
    memset(b,0,sizeof(b)); max=0;
    for(int i=1;i<=n;i++)
    {
    k=0;
    for(int j=1;j<=i;j++)
    if( ( f[i]>f[j] ) && ( k<b[j] ) ) k=b[j];
    b[i]=k+1;
    if(b[i]>max) max=b[i];
    }
    printf("%d",max-1);
    return 0;
    }

  • 0
    @ 2017-07-30 13:16:35

    Var
    s:string;
    i,j,l,num,max,k:longint;
    a,f:array[1..10000]of longint;
    ch:boolean;
    Begin
    readln(s);
    l:=1;
    for i:=1 to length(s) do
    begin
    if s[i]=',' then
    inc(l)
    else
    if s[i]in ['0'..'9'] then
    a[l]:=a[l]*10+(ord(s[i])-48);
    end;
    for i:=1 to l do
    f[i]:=1;
    for i:=2 to l do
    for j:=1 to i-1 do
    if (a[i]<a[j]) and (f[j]+1>f[i]) then 之前这里少加了一个判断所以没过
    f[i]:=f[j]+1;
    max:=-1;
    for i:=1 to l do
    if max<f[i] then
    max:=f[i];
    write(max,',');
    fillchar(f,sizeof(f),0);
    k:=1;
    while k<=l do
    begin
    ch:=false;
    for i:=1 to num do
    if a[k]<f[i] then
    begin
    ch:=true;
    f[i]:=a[k];
    break;
    end;
    if not ch then
    begin
    inc(num);
    f[num]:=a[k];
    end;
    inc(k);
    end;
    writeln(num-1);
    readln;
    End.

  • 0
    @ 2016-11-15 20:11:26

    注意对DILWORTH定理的理解
    找出反链的特征:递增还是非降?
    #include <iostream>
    using namespace std;

    int main(){
    freopen("in.txt","r",stdin);
    int n=1,a[25],f1[25]={0},f2[25]={0};
    char c;
    cin>>a[1];
    while(cin>>c)
    cin>>a[++n];
    for(int i=2;i<=n;i++)
    for(int j=1;j<i;j++)
    if(a[j]>=a[i]&&f1[i]<f1[j]+1)
    f1[i]=f1[j]+1;
    int ans=0;
    for(int i=1;i<=n;i++)
    ans=ans>f1[i]?ans:f1[i];
    cout<<ans+1<<",";
    for(int i=2;i<=n;i++)
    for(int j=1;j<i;j++)
    if(a[j]<a[i]&&f2[i]<f2[j]+1)
    f2[i]=f2[j]+1;
    ans=0;
    for(int i=1;i<=n;i++)
    ans=ans>f2[i]?ans:f2[i];
    cout<<ans+1-1;

    return 0;
    }

  • 0
    @ 2016-08-16 17:27:45

    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    int a[22];
    int d1[22];
    int d2[22];
    int main(){
    char c=',';
    int n=0;
    memset(d1,0,sizeof(d1));
    memset(d2,0,sizeof(d2));
    int ans1=0,ans2=0;
    while(c!='\n'){ cin>>a[n++];c=getchar();}
    for(int i=0;i<n;i++){
    d1[i]=1;d2[i]=1;
    for(int j=0;j<i;j++){
    if(a[j]>a[i]) d1[i]=max(d1[i],d1[j]+1);
    if(a[j]<=a[i]) d2[i]=max(d2[i],d2[j]+1);
    }
    ans1=max(ans1,d1[i]);
    ans2=max(ans2,d2[i]);
    }
    cout<<ans1<<','<<ans2-1;
    return 0;
    }

  • 0
    @ 2016-07-22 18:06:47

    第二问思路来自楼上
    ```pascal
    uses math;
    const n10:array[0..7] of longint=(1,10,100,1000,10000,100000,1000000,10000000);
    var a:array[1..20] of record
    data,long:longint;
    end;
    i,j,k,l,n:longint;inp:ansistring;

    begin
    fillchar(a,sizeof(a),0);
    readln(inp);i:=1;j:=1;l:=0;n:=0;
    while j<length(inp) do begin
    inc(l);
    for j:=i+1 to length(inp)+1 do if inp[j]=',' then break;
    for i:=i to j-1 do inc(a[l].data,(ord(inp[i])-ord('0'))*n10[j-i-1]);
    i:=j+1;
    end;{check input data
    writeln(l);
    for i:=1 to l do write(a[i].data,' ');}
    for i:=1 to l do a[i].long:=1;
    for i:=l-1 downto 1 do
    for j:=i+1 to l do
    if (a[j].data<=a[i].data) then
    a[i].long:=max(a[j].long+1,a[i].long);
    j:=a[1].long;
    for i:=1 to l do j:=max(a[i].long,j);
    for i:=1 to l do a[i].long:=1;
    for i:=l-1 downto 1 do
    for k:=i+1 to l do
    if ((a[k].data>a[i].data) and (a[i].long<a[k].long+1)) then
    a[i].long:=a[k].long+1;
    for i:=1 to l do n:=max(a[i].long,n);
    writeln(j,',',n-1);
    end.
    ```

  • 0
    @ 2016-07-19 12:37:35

    第一问是很显然的**最长不下降序列**。
    第二问应用**Dilworth定理**,*最少链划分数* = 最长反链长度
    在本题,**最长反链长度**即是**最长不上升序列长度**。
    另外,利用*lower_bound()*函数可使代码更优美。
    时间复杂度**O(n log n)**。

    #include<cstdio>
    #include<algorithm>
    #include<cstdlib>
    #include<cstring>
    #include<iostream>
    #include<string>
    using namespace std;
    
    const int maxn=1010;
    const int INF=1e9;
    
    int a[maxn],f[maxn],n=1;
    char c;
    
    int main()
    {
        //freopen("c.in","r",stdin);
        //freopen("c.out","w",stdout);
        
        while(cin>>a[n]>>c)n++;
        
        //for(int i=1;i<=n;i++)printf("%d ",a[i]);
        
        fill(f+1,f+n+1,INF);
        for(int i=1;i<=n;i++)
        *lower_bound(f+1,f+n+1,a[i])=a[i];
        
        int ans1=lower_bound(f+1,f+n+1,INF)-f-1;
        
        fill(f+1,f+n+1,INF);
        for(int i=n;i>=1;i--)
        *lower_bound(f+1,f+n+1,a[i])=a[i];
        
        int ans2=lower_bound(f+1,f+n+1,INF)-f-1;
        
        printf("%d,%d",ans2,ans1-1);
        
        return 0;
    }
    
    • @ 2016-11-02 11:55:20

      最长不降的话,应该用 upper_bound 而不是 lower_bound

  • 0
    @ 2016-05-18 23:33:17

    第二问为啥是最长上升子序列????
    ```c++
    #include <cstdio>
    #include <iostream>

    int main(){
    freopen("in.txt","r",stdin);
    int n=1,a[30];
    char c;
    while(std::cin>>a[n]>>c)
    n++;
    int f[30],f2[30];
    for(int i=1;i<=n;i++){
    f[i]=1;
    f2[i]=1;
    }

    for(int i=n-1;i>=1;i--)
    for(int j=n;j>=i+1;j--)
    if(a[i]>=a[j]&&f[i]<f[j]+1){
    f[i]=f[j]+1;
    }
    for(int i=2;i<=n;i++)
    for(int j=1;j<=i-1;j++){
    if(a[i]>a[j]&&f2[i]<f2[j]+1)
    f2[i]=f2[j]+1;
    }
    int max=0;
    for(int i=1;i<=n;i++)
    max=max>f[i]?max:f[i];
    printf("%d,",max);
    max=0;
    for(int i=1;i<=n;i++)
    max=max>f2[i]?max:f2[i];
    printf("%d",max-1);
    return 0;
    }
    ```

  • 0
    @ 2016-05-08 15:52:29

    var
    f,w:array[1..100]of integer;
    i,j,n,m,now:integer;
    function search(p:integer):integer;
    var
    i,t,m:integer;
    begin
    if f[p]>0 then exit(f[p]);
    m:=1;
    for i:=p+1 to n do begin
    if w[i]<w[p] then begin
    t:=search(i)+1;
    if m<t then begin
    m:=t;
    end;
    end;
    end;
    f[p]:=m;
    exit(m);
    end;
    function search2(p:integer):integer;
    var
    i,t,m:integer;
    begin
    m:=1;
    for i:=p+1 to n do begin
    if w[i]>w[p] then begin
    t:=search2(i)+1;
    if m<t then m:=t;
    end;
    end;
    f[p]:=m;
    exit(m);
    end;
    begin
    n:=0;
    while not eof do begin
    inc(n);
    read(w[n]);
    end;
    m:=0;
    for i:=1 to n do begin
    j:=search(i);
    if j>m then m:=j;
    end;
    writeln(m);
    m:=0;
    fillchar(f,0,sizeof(f));
    for i:=1 to n do begin
    j:=search2(i);
    if m<j then m:=j;
    end;
    writeln(m);
    end.

  • 0
    @ 2016-03-26 14:16:11

    var
    f,a:array[0..20] of longint;
    s:ansistring;
    p,n,i,j,ans1,ans2:longint;
    begin
    readln(s);
    p:=pos(',',s);
    while p>0 do
    begin
    inc(n);
    val(copy(s,1,p-1),a[n]);
    delete(s,1,p);
    p:=pos(',',s);
    end;
    inc(n);
    val(s,a[n]);
    fillchar(f,sizeof(f),0);
    for i:=1 to n do
    begin
    f[i]:=1;
    for j:=1 to i-1 do
    if (a[j]>=a[i]) and (f[j]+1>f[i]) then f[i]:=f[j]+1;
    if f[i]>ans1 then ans1:=f[i];
    end;
    fillchar(f,sizeof(f),0);
    for i:=1 to n do
    begin
    f[i]:=1;
    for j:=1 to i-1 do
    if (a[j]<a[i]) and (f[j]+1>f[i]) then f[i]:=f[j]+1;
    if f[i]>ans2 then ans2:=f[i];
    end;
    writeln(ans1,',',ans2-1);
    end.

  • 0
    @ 2015-11-04 16:29:12

    #include<iostream>
    #include<cmath>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int h[100],f[100],n,x,tot;
    int work1()
    {
    f[1]=1;
    int ans=0;
    memset(f,0,sizeof(f));
    for(int i=1;i<=tot;i++){
    f[i]=1;/*重中之重*/
    for(int j=1;j<i;j++){
    if(h[j]>=h[i])f[i]=max(f[i],f[j]+1);
    }
    ans=max(ans,f[i]);
    }
    return ans;
    }
    int work2()
    {
    int ans2=0;
    memset(f,0,sizeof(f));
    for(int i=1;i<=tot;i++){
    f[i]=1;/*重中之重*/
    for(int j=1;j<i;j++){
    if(h[j]<h[i])f[i]=max(f[i],f[j]+1);
    }
    ans2=max(ans2,f[i]);
    }
    return ans2-1;
    }
    int main()
    {
    tot=0;
    scanf("%d",&x);h[++tot]=x;
    while(scanf(",%d",&x)){
    h[++tot]=x;
    }
    cout<<work1()<<',';
    cout<<work2();
    }
    之前一直没发现,后来发现f[i]本身赋初值时应为1。

  • 0
    @ 2015-11-02 17:57:09

    第一问直接最长不上升子序列
    第二问Dilworth定理
    最少链划分 = 最长反链长度
    最少系统 = 最长导弹高度上升序列长度
    最后记着减去1
    ###Block code
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    const int N=5000;
    int a[N],n;
    int sta[N],top;
    bool cmp(int a,int b)
    {return a>b;}
    void work1()
    {
    for(int i=1;i<=n;i++)
    {
    if(top==0||a[i]<=sta[top-1])sta[top++]=a[i];
    else
    *upper_bound(sta,sta+top,a[i],cmp)=a[i];
    }
    cout<<top<<",";
    }
    void work2()
    {
    top=0;
    memset(sta,0,sizeof sta);
    for(int i=1;i<=n;i++)
    {
    if(top==0||a[i]>sta[top-1])sta[top++]=a[i];
    else
    *lower_bound(sta,sta+top,a[i])=a[i];
    }
    cout<<top-1<<endl;
    }
    int main()
    {
    while(scanf("%d,",&a[++n])!=EOF);
    n--;
    work1();
    work2();
    }

  • 0
    @ 2015-10-31 16:40:15

    有没有很多人骂逗号骂了很久的,一个诡异的想法,先上代码:
    FILE*f;
    f=fopen("xxx.txt","w");
    int i;
    char s[1000];
    scanf("%s",s);
    int len=strlen(s);
    for(i=0;i<len;i++)
    {
    if(s[i]==',')
    {

    s[i]=' ';
    n+=1;
    }
    }
    fprintf(f,"%s",s);
    fclose(f);
    f=fopen("xxx.txt","r");
    for(i=1;i<=n;i++)
    fscanf(f,"%d",&A[i]);
    用文件。。。。我也不知道怎么想的。。。反正就是用文件了。。。然后过了。。。。A里就存的是数字了,没有逗号

  • 0
    @ 2015-08-30 00:30:00

    不知道算法思想对不对...
    自然,用*最少的系统打下最多的导弹*,那么就需要 每个系统 打下 尽可能多 的导弹。所以就一直LIS,直到所有导弹被击落。
    每做一次LIS就 用**回溯**的方法 将打下的导弹做个标记,这样下次dp时就会忽略这些数据。
    ###Block Code
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;

    int cnt=0,rest,ans=0,f[30],a[30],maxn,index[30];//index is used to track the missles shot down in some round.
    bool flag[30];
    char chr=0;

    void dp(){
    int k,pick;
    maxn=-1;
    for(int i=0;i<cnt;i++)
    index[i]=i;
    for(int i=0;i<cnt;i++){
    if(!flag[i])//If the missle has been shot down, then leave it.
    continue;
    pick=i;//Caution!
    for(int j=0;j<i;j++){
    if(!flag[j])//Ignore the shot-down missles.
    continue;
    if(f[i]<f[j]+1&&a[i]<=a[j]){
    f[i]=f[j]+1;
    pick=j;//Remember where is f[i] from.
    }
    }
    index[i]=pick;//The one before missle <i> is missle <pick>.
    }
    for(int i=cnt-1;i>=0;i--){//Find out how many missles at most can be shot down in this round.
    if(maxn<f[i]){
    maxn=f[i];k=i;
    }
    }
    do{
    flag[k]=false;//Mark the shot-down missles.
    k=index[k]; //Keep tracking.
    rest--; //Fewer missles left.
    } while(k!=index[k]);
    if(flag[k]){//Caution! Very EGG-PAIN here.
    rest--;
    flag[k]=false;
    }
    }

    int main(){
    //freopen("input.txt","r",stdin);
    memset(a,0,sizeof(a));
    while(scanf("%d",&a[cnt++])!=EOF){
    chr=getchar();//read the god-damn comma.
    f[cnt-1]=1;flag[cnt-1]=true;//Initialization.
    }
    rest=--cnt;//There's <rest> missles left.
    dp();
    printf("%d,",maxn);
    while(rest>0){
    ans++;//Need 1 more anti-missle system.
    fill(f,f+cnt,1);//Initialization.
    dp();
    }
    printf("%d\n",ans);
    //fclose(stdin);
    return 0;
    }

    • @ 2016-11-16 09:56:26

      无敌 我用upper_bound无法排掉这些a[i]...

  • 0
    @ 2015-08-21 23:22:53

    #include <iostream>
    #include <stdio.h>
    #include <string.h>

    using namespace std;

    int a[20 + 2][20 + 2];
    int f[20 + 2];
    int i , j;
    int n , m;
    int x;
    bool flag;
    int pre[20 + 2];
    int pos = 1;
    int ans;

    int main()
    {
    while( scanf( "%d," , &x ) != EOF && x != -1 )
    a[ ++i ][1] = x;
    n = i;
    while( n )
    {
    memset( pre , 0 , sizeof( pre ) );
    for( i = 1 ; i <= n ; i++ )
    f[i] = 1;

    for( i = 1 ; i <= n ; i++ )
    for( j = 1 ; j < i ; j++ )
    if( a[j][ pos ] >= a[i][ pos ] )
    if( f[j] + 1 > f[i] )
    {
    pre[i] = j;
    f[i] = f[j] + 1;
    }
    m = n;
    while( n )
    {
    a[n][ pos ] = -1;
    n = pre[n];
    }
    for( i = 1 , j = 1 ; i <= m ; i++ )
    if( a[i][ pos ] != -1 )
    a[ j++ ][ pos + 1 ] = a[i][ pos ];
    n = j - 1;
    pos++;
    if( !flag )
    {
    flag = 1;
    int ans = 0;
    for( i = 1 ; i <= m ; i++ )
    ans = max( ans , f[i] );
    cout << ans << ",";
    }
    ans++;
    }
    cout << ans - 1 << endl;
    system( "pause" );
    return 0;
    }
    为什么要这样输入!!!

  • 0
    @ 2015-07-29 21:53:50

    记录信息
    评测状态 Accepted
    题目 P1303 导弹拦截
    递交时间 2015-07-29 21:52:22
    代码语言 C++
    评测机 VijosEx
    消耗时间 30 ms
    消耗内存 280 KiB
    评测时间 2015-07-29 21:52:25
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 276 KiB, score = 16
    测试数据 #1: Accepted, time = 15 ms, mem = 276 KiB, score = 16
    测试数据 #2: Accepted, time = 0 ms, mem = 280 KiB, score = 16
    测试数据 #3: Accepted, time = 0 ms, mem = 280 KiB, score = 18
    测试数据 #4: Accepted, time = 15 ms, mem = 280 KiB, score = 16
    测试数据 #5: Accepted, time = 0 ms, mem = 276 KiB, score = 18
    Accepted, time = 30 ms, mem = 280 KiB, score = 100
    代码
    #include <iostream>
    #include <stdio.h>
    using namespace std;
    int a[25];
    int ans[25];
    int main()
    {
    int n;
    ans[0]=1000000;
    scanf("%d",&a[1]);
    for(n=2;;n++)
    { char c;
    scanf("%c",&c);
    if(c!=',')
    break;
    scanf("%d",&a[n]);
    }
    n--;
    int now=1;
    int maxn=0;
    for(int i=1;i<=n;i++)
    {
    if(a[i]<=ans[now-1])ans[now++]=a[i];
    else
    {
    int j;
    for(j=now-1;j>=1;j--)
    if(a[i]<=ans[j-1])
    {
    ans[j]=a[i];
    break;
    }
    continue;

    }
    maxn++;
    }
    printf("%d,",maxn);
    now=1;
    maxn=0;
    for(int i=n;i>=1;i--)
    {
    if(a[i]<=ans[now-1])ans[now++]=a[i];
    else
    {
    int j;
    for(j=now-1;j>=1;j--)
    if(a[i]<=ans[j-1])
    {
    ans[j]=a[i];
    break;
    }
    continue;

    }
    maxn++;
    }
    printf("%d",maxn-1);

    }

信息

ID
1303
难度
6
分类
动态规划 | 单调性DP 点击显示
标签
递交数
7497
已通过
2001
通过率
27%
被复制
7
上传者