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

懂的都懂 可以运用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;
} 

坏掉了坏掉了，最长上升都写错了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;
}

#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;
}

#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;
}

#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;
}

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.

注意对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;
}

#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;
}

第二问思路来自楼上
```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.
```

第一问是很显然的**最长不下降序列**。
第二问应用**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;
}

第二问为啥是最长上升子序列？？？？
```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;
}
```

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.

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.

#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。

第一问直接最长不上升子序列
第二问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();
}

有没有很多人骂逗号骂了很久的，一个诡异的想法，先上代码：
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里就存的是数字了，没有逗号

不知道算法思想对不对...
自然，用*最少的系统打下最多的导弹*，那么就需要 每个系统 打下 尽可能多 的导弹。所以就一直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;
}

#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;
}
为什么要这样输入！！！

记录信息
评测状态 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);

}