1 条题解

  • -1

    #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

信息

ID
1466
难度
9
分类
(无)
标签
递交数
9
已通过
3
通过率
33%
上传者