前十个过了,后面就全TLE了……救救孩子吧
#include<stdio.h>
#include<math.h>
int max(int, int);
int search(int*,int,int);
int dd[100003]={0};//导弹高度
int most[100003]={1};//以各导弹为结尾的最长不升子列的长度
int main(void)
{
int times = 0;
char ch;
while (times>=0)//输入导弹高度
{
scanf("%d", &dd[times++]);
ch = getchar();
if(ch=='\n')
break;
}
for (int i = 0; i < times; i++)//初始化most为1
most[i] = 1;
for(int i=1;i<times;i++)//动态规划求最长
{
for(int j=0;j<i;j++)
{
if(dd[i]<=dd[j])
{
most[i]=max(most[i],(most[j]+1));
}
else continue;
}
}
int ans=most[0];
for(int i=0;i<times;i++)//判断哪个不升子列最长
{
if(ans<=most[i])
ans=most[i];
}
printf("%d\n", ans); /*第一问结束*/
int height[100000]={0,dd[0]};//各拦截系统的最大高度
int nlj = 1; //拦截系统数
for(int i=1;i<times;i++)
{
if(dd[i]>height[nlj]) //超出上限,需要新的拦截系统
{
nlj++;
height[nlj]=dd[i];
}
else{ //不需要新拦截系统,二分定位导弹由哪个拦截
int back = search(height,nlj,dd[i]);
height[back]=dd[i];
}
}
printf("%d", nlj); /*第二问结束*/
return 0;
}
int max(int a, int b)
{
if(a>=b)
return a;
else
return b;
}//第一题两个数比大小
int search(int* first, int nlj,int inp)
{
int low=0; //编号下限
int high=nlj;//编号上限
while(high-low>1)
{
int mid = (low+high)/2;
if(inp<first[mid])
high=mid;
else
low=mid;
}
return high;
}//第二问二分
求求了