#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int a[10000][4];
int w[10000];//定义无限高
int n=1;//n为导弹数量
int main()
{
scanf("%d",&a[1][1]);
a[1][2]=1;
a[1][3]=0;
int x;
char b;
for(int i=2;i<=30000;i++)
{
if(scanf("%c",&b)==1&&int(b)==44)
{
scanf("%d",&x);
n++;
a[n][1]=x;//输入这个数本身
a[n][2]=1;//假设这个数后跟的序列长度为1
a[n][3]=0;//假设这个数后面没有数列

}
else
break;
}
/*while(scanf("%d",&x)==1)//依次输入导弹
{
n++;
a[n][1]=x;//输入这个数本身
a[n][2]=1;//假设这个数后跟的序列长度为1
a[n][3]=0;//假设这个数后面没有数列
}*/

memset(w,40000,sizeof(w));

for(int i=n-1;i>=1;i--)
{
int lon=0;//长度
int k=0;//转移下标
for(int j=i+1;j<=n;j++)
{
if(a[i][1]>=a[j][1]&&a[j][2]>lon)
{
lon=a[j][2];
k=j;
}

if(lon>0)
{
a[i][2]=lon+1;
a[i][3]=k;
}
}

}

int max1;
for(int i=1;i<=n;i++)
{
if(max1<a[i][2])
{
max1=a[i][2];
}

}
cout<<max1<<",";
//贪心算法
/*最多有三十套导弹系统，每一次用射程最低的导弹打*/
for(int e=1;e<=n;e++)//枚举导弹
{
sort(w+1,w+n+1);
for(int r=1;r<=n;r++)//枚举反导系统
if(w[r]>a[e][1])
{
w[r]=a[e][1];
break;
}
}
int k=0;
for(int i=1;i<=10002;i++)
{
sort(w+1,w+n+1);
if(w[i]>40000)//说明此导弹系统还没有被用过，
{
k=i;
break;
}
}
cout<<k-2;
return 0;

}

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.

呵呵，加一个字符串处理就行了。
刷水题一遍过，有利于增长信心。
希望明天NOIP复赛一路走好！
（PS：呵呵）

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 556 KiB, score = 16
测试数据 #1: Accepted, time = 0 ms, mem = 560 KiB, score = 16
测试数据 #2: Accepted, time = 0 ms, mem = 560 KiB, score = 16
测试数据 #3: Accepted, time = 0 ms, mem = 564 KiB, score = 18
测试数据 #4: Accepted, time = 0 ms, mem = 560 KiB, score = 16
测试数据 #5: Accepted, time = 0 ms, mem = 552 KiB, score = 18
Accepted, time = 0 ms, mem = 564 KiB, score = 100

膜拜话说楼下下下下的神做法。。。。。。ORZ....
本弱实在不懂得为什么第二问是求最长上升自序列，所以手残了网络流555。
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 564 KiB, score = 16
测试数据 #1: Accepted, time = 0 ms, mem = 556 KiB, score = 16
测试数据 #2: Accepted, time = 0 ms, mem = 556 KiB, score = 16
测试数据 #3: Accepted, time = 15 ms, mem = 568 KiB, score = 18
测试数据 #4: Accepted, time = 0 ms, mem = 564 KiB, score = 16
测试数据 #5: Accepted, time = 0 ms, mem = 556 KiB, score = 18
Accepted, time = 15 ms, mem = 568 KiB, score = 100

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>

using namespace std;

#define MAXN 21
#define inf 0x7fffffff
#define MAXV 50

struct edge {
edge *pair,*next;
int t,f;
edge () {
pair=next=NULL;
}
} *head[MAXV];

void Add(int s,int t,int f) {
edge *p=new(edge);
p->t=t;
p->f=f;
p->next=head[s];
head[s]=p;
}

void AddEdge(int s,int t,int f) {
Add(s,t,f);
Add(t,s,0);
head[s]->pair=head[t];
head[t]->pair=head[s];
}

int n=0,V=0,S,T;
int H[MAXN],v[MAXN][2];

void INIT() {
while (1) {
scanf("%d",&H[++n]);
if (getchar()!=int(',')) break;
}
for (int i=0;i++<n;) {
v[i][0]=++V;
v[i][1]=++V;
}
S=++V;T=++V;
memset(head,0,sizeof(head));
for (int i=0;i++<n;) {
for (int j=i;j++<n;) {
if (H[i]>=H[j]) {
AddEdge(v[i][0],v[j][1],1);
}
}
}
for (int i=0;i++<n;) {
AddEdge(S,v[i][0],1);
AddEdge(v[i][1],T,1);
}
}

int f[MAXN];

int Dp() {
for (int i=0;i++<n;) f[i]=1;
for (int i=0;i++<n;) {
for (int j=0;j++<i-1;) {
if (H[j]>=H[i]) {
f[i]=max(f[i],f[j]+1);
}
}
}
int ans=0;
for (int i=0;i++<n;) ans=max(ans,f[i]);
return ans;
}

int h[MAXV],gap[MAXV];
edge *d[MAXV];

int sap(int v,int flow) {
if (v==T) return flow;
int rec=0;
for (edge *p=d[v];p;p=p->next) if (p->f&&h[v]==h[p->t]+1) {
int ret=sap(p->t,min(flow-rec,p->f));
p->f-=ret,p->pair->f+=ret;
d[v]=p;
if ((rec+=ret)==flow) return flow;
}
if (!(--gap[h[v]])) h[S]=T;
gap[++h[v]]++,d[v]=head[v];
return rec;
}

int maxflow() {
memset(h,0,sizeof(h));
memset(gap,0,sizeof(gap));
gap[0]=T;
for (int i=0;i++<T;) d[i]=head[i];
int flow=0;
while (h[S]<T) flow+=sap(S,inf);
return flow;
}

int main() {
INIT();
printf("%d,%d\n",Dp(),n-maxflow()-1);
return 0;
}

擦，这题怎么改了，原来不是先读入一个数！！！！

program p1303;
uses math;
var
f,a:array[0..25]of longint;
ma,mi,n,i,j:longint;
ss,s:ansistring;
begin
readln(ss); ss:=ss+',';
n:=0;
for i:=1 to length(ss)do
begin
if ss[i]=',' then
begin
inc(n);
val(s,a[n]);
s:='';
end else
s:=s+ss[i];
end;

fillchar(f,sizeof(f),0);
f[1]:=1;
ma:=f[1];
for i:=2 to n do
begin
for j:=1 to i-1 do
if (a[j]>=a[i]) and (f[i]<f[j]) then f[i]:=f[j];
inc(f[i]);
ma:=max(ma,f[i]);
end;
fillchar(f,sizeof(f),0);
f[1]:=1;
mi:=1;
for i:=2 to n do
begin
for j:=1 to i-1 do
if (a[j]<a[i]) and (f[i]<f[j]) then f[i]:=f[j];
inc(f[i]);
mi:=max(mi,f[i]);
end;
writeln(ma,',',mi-1);
end.

//就是输入有点坑爹。。。。。

谁能证明下第二个解为什么是求最长上升子序列

来冒个泡……
第一问就是最长不升子序列，经典问题，可以用二分做到O(NlogN)。
第二问有一个贪心做法，从左到右考虑每个导弹，如果当前没有一套系统或者当前的任意系统都无法拦截，则新增一套系统，否则用能拦截当前导弹的拦截高度最小的导弹来拦截当前导弹。使用平衡树维护可以达到O(NlogN)的复杂度，用C++的set可以很方便地实现。
总复杂度就是O(NlogN)的了。

//Template
#include <cstdio>
#include <climits>
#include <iostream>
#include <set>
using namespace std;

#define N 100
int n, a[N + 1], x, q[N + 1], tot = 0;
set <int> h;
set <int> :: iterator it;

int main() {

while (scanf("%d%*c", &x) != EOF) a[++n] = x;

q[0] = INT_MAX;
for (int i = 1; i <= n; ++i)
if (!tot || q[tot] >= a[i]) q[++tot] = a[i];
else {
int l = 0, r = tot;
while (l < r) {
int mid = l + r + 1 >> 1;
if (q[mid] >= a[i]) l = mid;
else r = mid - 1;
}
q[l + 1] = max(q[l + 1], a[i]);
}

for (int i = 1; i <= n; ++i) {
it = h.lower_bound(a[i]);
if (it == h.end()) h.insert(a[i]);
else {
h.erase(it);
h.insert(a[i]);
}
}

cout << tot << "," << h.size() - 1 << endl;

fclose(stdin);
fclose(stdout);
return 0;
}

编译成功
测试数据 #0: Accepted, time = 0 ms, mem = 464 KiB, score = 16
测试数据 #1: Accepted, time = 0 ms, mem = 468 KiB, score = 16
测试数据 #2: Accepted, time = 0 ms, mem = 468 KiB, score = 16
测试数据 #3: Accepted, time = 0 ms, mem = 468 KiB, score = 18
测试数据 #4: Accepted, time = 0 ms, mem = 468 KiB, score = 16
测试数据 #5: Accepted, time = 0 ms, mem = 468 KiB, score = 18
Accepted, time = 0 ms, mem = 468 KiB, score = 100
/**********************************
User:Kevin.Deng
Date:2013.07.24
Lang:C++
Prog:Vijos1303&&NOIP1999普及组
Scho:HNSDFZ
**********************************/
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
using namespace std;
#define ufor(i,j,k) for (int i=j;i<=k;i++)
#define dfor(i,j,k) for (int i=j;i>=k;i--)
#define m_int 2147483647
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define pi 3.1415926535897
#define re return 0
#define pn printf("\n")
#define ll long long
#define real double
int n,m;
int max1,max2;
int s;
int a[50],b[50],c[50],d[50];
int f[50],f1[50];
int g[50];
void file_o()
{
freopen(".","r",stdin);
freopen(".","w",stdout);
}
void file_c()
{
fclose(stdin);fclose(stdout);
}
void init()
{
scanf("%d",&a[1]);
n=1;
while (scanf(",%d",&a[n+1])==1)
n++;
}
void work()
{
ufor(i,1,n)f[i]=1;
dfor(i,n-1,1)
ufor(j,i+1,n)
if (a[i]>=a[j])
if (f[j]+1>f[i])
{
f[i]=f[j]+1;
b[i]=j;
}
max1=0;
//ufor(i,1,n)
//printf("%d ",f[i]);
//pn;
ufor(i,1,n)
if(f[i]>max1)
{
max1=f[i];
s=i;
}
for(int i=s;i!=0;i=b[i])
c[i]=1;
m=0;
ufor(i,1,n)
if (c[i]==0)
d[++m]=a[i];
//ufor(i,1,m)
//printf("%d ",d[i]);
//pn;
ufor(i,1,m)
f1[i]=1;
dfor(i,m-1,1)
ufor(j,i+1,m)
if (d[i]<d[j])
f1[i]=max(f1[i],f1[j]+1);
max2=0;
ufor(i,1,m)
max2=max(max2,f1[i]);

}
void outp()
{
printf("%d,%d",max1,max2);
}
int main()
{
//file_o();
init();
work();
outp();
//file_c();
re;
}

#include <cstdio>
#include <cstring>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <stack>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define abs(x) ((x)>0?(x):-(x))
#define __max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,repstt,repend) for(int i=repstt;i<repend;i++)
#define erep(i,repstt,repend) for(int i=repstt;i<=repend;i++)
#define inf 0x7f//2147483647
#define iinf 0x7fffffff
#define PI acos(-1.0)
#define NOBUG puts("No_Bug_Hear");
#define STOP system("pause");
#define FOUT freopen("out.txt","w",stdout);
#define FIN freopen("in.txt","r",stdin);
#define OUTCLOSE fclose(stdout);
#define INCLOSE fclose(stdin);
#define INIT(a,b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int f[30],dp[30],cnt=1;
char tch;
int main(){
//FIN
//FOUT
rep(i,0,30)dp[i]=1;
scanf("%d",f);
while(scanf(",%d",&f[cnt])==1)
cnt++;
rep(i,0,cnt)
rep(j,0,i)
if(f[j]>=f[i])
dp[i]=max(dp[i],dp[j]+1);
int tmax=-1;
rep(i,0,cnt)
tmax=__max(dp[i],tmax);
rep(i,0,30)dp[i]=1;
rep(i,0,cnt)
rep(j,0,i)
if(f[j]<f[i])
dp[i]=__max(dp[i],dp[j]+1);
cout<<tmax<<",";
tmax=-1;
rep(i,0,cnt)
tmax=__max(dp[i],tmax);
cout<<tmax-1<<endl;
//INCLOSE
//OUTCLOSE
return 0;
}

第一问最长不升子序列，第二问最长只升子序列

点击查看代码

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

有点2了

我第2问用匹配的。

反正AC了

++++++++++++++引用某神牛++++++++++++++++++++++++++++

第二问显然要难一点，最直观的算法是贪心，但是反例也容易找到，如：

6 5 1 7 3 2

如果第一次打6 5 3 2,显然还要打两次，而最好的方案是6 5 1/7 3 2。

显然失败之处在于第一种方案为了多打3和2，把1和7隔断了，

但事实上把3和2留给第二套打

还不是一样！因为每个导弹都要打到，故我们应该把注意力放在“打到每一枚导弹”。

在上一个例子中，7是必须打到的，

因为它是最高的，所以必有一次拦截是以7开头的！！！

既然是必须，那么打7的同时顺便打一打其他的绝对不比不打差！那么打哪些呢？

下面说明：应该打后面导弹中最高的一个K。

先定义一个概念：把当前能打的最大高度叫做“能力”

理由如下：

对于K以后的导弹，绝对该打K，因为对于K以后的导弹，不打K时能打到的，打了K也能打到（K是最高的嘛！）,

K等于是“白打”，而对于7和K之间的导弹，打了任何一个就一定不能再打K了（K最高嘛！）反正中间的和

K不能一次打，先打不会比后打差！

类似的，下一个目标是K后面的最高的。

~~~~~~~~~~~~~~~~~dig ~~~~~~~·沙茶分割线~~~~~~~~~~~~~~~~~~~

var a:array[1..30] of longint;

f:array[0..50] of longint;

d:array[1..50,1..2] of longint;

i,j,n,m,sum,l,k,max,x,ans:longint;

c:char;

s,t,st:string;

procedure findmax;

var k:longint;

begin

max:=0;

for k:=i to n do if a[k]>max then

begin

max:=a[k];

l:=k;

end;

end;

begin

assign(input,'e:\p1.in');

assign(output,'e:\p1.out');

reset(input);

rewrite(output);

i:=1;

readln(s);

if pos(',',s)=0 then

begin

writeln('1,0');

close(input);

close(output);

halt;

end;

while s'' do

begin

l:=pos(',',s);

if l=0 then

begin

val(s,a[i]);

break;

end;

t:=copy(s,1,l-1);

val(t,a[i]);

inc(i);

delete(s,1,l);

end;

n:=i;

for i:=1 to n do f[i]:=1;

f[n]:=1;

for i:=n-1 downto 1 do

begin

max:=0;

for j:=i+1 to n do

begin

if (a[i]>a[j]) and (f[j]>max) then

begin

max:=f[j];

m:=j;

end;

if max0 then

f[i]:=f[m]+1;

end;

end;

max:=0;

for i:=1 to n do if f[i]>max then max:=f[i];

write(max,',');

i:=1;

sum:=0;

ans:=-1;

while sum

var

s,s1:string;

f,a,c:array[1..20]of integer;

i,j,n,max,posi,sum,maxn,maxxx:integer;

flag:array[1..20]of boolean;

procedure del(k:integer);

begin

flag[k]:=true;

if (f[k]>1) then del(c[k]);

end;

begin

{assign(input,'in.txt');

assign(output,'out.txt');

reset(input);

rewrite(output);}

readln(s);

posi:=pos(',',s);

while not (posi=0) do begin

inc(i);

s1:=copy(s,1,posi-1);

val(s1,a[i]);

delete(s,1,posi);

posi:=pos(',',s);

end;

val(s,a);

n:=i+1;

while not (sum=n) do begin

for i:=1 to n do if flag[i] then f[i]:=0 else f[i]:=1;

for i:=n downto 1 do

for j:=n downto (i+1) do

if (not flag[i])and (not flag[j]) then begin

if (a[i]>=a[j])and(f[i]maxxx then maxxx:=f[i];

for i:=1 to n do if (f[i]=maxxx) then begin del(i);break;end;

if maxxx>max then max:=maxxx;

inc(sum,maxxx);

maxxx:=0;

inc(maxn);

end;

writeln(max,',',maxn-1);

end.

我的策略：一遍一遍找最长不下降序列，每次都将序列中的元素标记，当所有元素都被标记的时候，输出找过多少次就行了

破题让我交了n多多多多次....呜呜呜

program daodan;

var

a,b,h:array[1..20] of longint;

i,j,m,n,x:integer;

begin

repeat

　　inc(i);

　　read(a[i]);

　　for j:= 1 to i-1 do

　　 if a[j]>=a[i] then

　　　　if b[j]>b[i] then b[i]:=b[j];

　　inc(b[i]);

　　if b[i]>m then m:=b[i];

　　x:=0;

　　for j:=1 to n do

　　 if h[j]>=a[i] then

　　　　if x=0 then x:=j

　　　　 else if h[j]

var i,j,k,n,m,max:integer;

a,f,b:array[0..200]of integer;

pp:array[0..200]of boolean;

ff:boolean;

s:string;

function pd(x:longint):boolean;

var i:longint;

begin

pd:=true;

for i:=1 to x do if a[i]0 then begin pd:=false;break;end;

end;

begin

readln(s);

i:=1;

while pos(',',s)>0 do

begin

val(copy(s,1,pos(',',s)-1),a[i]);

delete(s,1,pos(',',s));

inc(i);

end;

val(s,a[i]);

n:=i;

ff:=true;

m:=0;

while not(pd(n)) do

begin

inc(m);

for i:=1 to n do

if a[i]0 then

begin

max:=1;

for j:=1 to i-1 do

if f[j]0 then

begin

if (f[j]+1>max)and(a[i]max then begin max:=f[i];k:=i;end;

if ff then begin write(max,',');ff:=false;end;

pp[k]:=true;

i:=b[k];

while i>0 do

begin

pp[i]:=true;

i:=b[i];

end;

for i:=1 to n do if pp[i] then begin pp[i]:=false;a[i]:=0;end;

fillchar(b,sizeof(b),0);

fillchar(f,sizeof(f),0);

end;

writeln(m-1);

end.

第一问…

n=1;max=0;

scanf("%d",&high[n]);

for(i=1;i=high[n]&&dp[i]+1>dp[n])

dp[n]=dp[i]+1;

}

max=dp[n];

while(scanf("%c",&d)!=EOF)

{

n++;

scanf("%d",&high[n]);

for(i=1;i=high[n]&&dp[i]+1>dp[n])

dp[n]=dp[i]+1;

}

if(dp[n]>max) max=dp[n];

}

printf("%d,",max+1);

同志们注意啦

“max+1”这里，如果是“max”,不加1，那样例就过，我试的别的数据也过，评测时第一问都比正确值大1；

如果是“max+1”,就AC，但样例第一问就少1，试的别的数据也少1。

我的天啊，这是什么数据啊，我要疯了

program p1303;

var

a,f:array[0..1000] of longint;

c:array[0..100,0..100] of integer;

n,m,i,j,k:longint;

st1:string;

max:longint;

procedure find;

var

i,j,k:longint;

begin

if n=0 then exit;

fillchar(f,sizeof(f),0);

fillchar(c,sizeof(c),0);

for i:=1 to n do

begin

k:=0;

if a[i]-maxlongint then

begin

for j:=i-1 downto 1 do

begin

if (a[j]maxlongint)and(f[j]>f[k])and(a[j]>=a[i]) then

k:=j;

end;

f[i]:=f[k]+1;

c[i]:=c[k];

inc(c);

c[i,c]:=i;

end;

end;

max:=1;

for i:=2 to n do

if f[i]>f[max] then max:=i;

if f[max]=-maxlongint then exit;

for i:=1 to c[max,0] do

a[c[max,i]]:=-maxlongint;

while (n>0)and(a[n]=-maxlongint) do dec(n);

inc(m);

find;

end;

begin

readln(st1);

i:=0;

m:=pos(',',st1);

while m0 do

begin

inc(i);

val(copy(st1,1,m-1),a[i],k);

delete(st1,1,m);

m:=pos(',',st1);

end;

inc(i);

val(st1,a[i],k);

n:=i;

if n=1 then begin writeln(1,',',0);exit;end;

fillchar(f,sizeof(f),0);

fillchar(c,sizeof(c),0);

for i:=1 to n do

begin

k:=0;

for j:=i-1 downto 1 do

begin

if (f[j]>f[k])and(a[j]>=a[i]) then

k:=j;

end;

f[i]:=f[k]+1;

c[i]:=c[k];

inc(c);

c[i,c]:=i;

end;

max:=1;

for i:=2 to n do

if f[i]>f[max] then max:=i;

write(f[max],',');

for i:=1 to c[max,0] do

a[c[max,i]]:=-maxlongint;

while (n>0)and(a[n]=-maxlongint) do dec(n);

m:=0;

find;

writeln(m);

end.