最后一条数据,一颗导弹

最后一条数据,一个导弹,所以逆推的童鞋要特判啊。。。。
动态规划+贪心
注意输入,建议输入字符串然后做字符串处理
#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 条评论

  • @ 2016-10-09 00:43:18

    vijos的题大多数据tai鬼畜

  • 1

信息

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