一看这道题就想到DP…但是我错误地认为当时的DP思路有后效性，没有敢打，最后改装了一下最长不降子序列，竟然对了～
【问题描述】
虽然msh长大了，但他还是和喜欢找点游戏自娱自乐。有一天，他在纸上写了一串数字：
1
,
1
,
2
,
5
,
4
。
接着他擦掉了一个1，结果发现剩下1,
2
,4都在自己所在的位置上，即1在第1位，2在第2位，4在第4位。
他希望擦掉某些数后，剩下的数列中在自己位置上的尽量多。他发现这个游戏很好玩，于是开始乐此不
疲地玩起来……不过他不能确定最多能有多少个数在自己的位置上，所有找到你，请你帮忙计算一下
!
【输入格式】
第1行：1个整数n，表示数列的长度。接下来一行为n个空格隔开的正整数，第i行表示Ai。
【输出格式】
一行一个整数，表示擦掉某些数后，最后剩下的数列中最多能有多少个数在自己的位置上，即Ai
=
i最
多能有多少。
【样例输入】
5
1
1
2
5
4
【样例输出】
3
【数据范围】
对于20
%
的数据，n
<=
20
；
对于60
%
的数据，n
<=
100
；
对于100
%
的数据，n
<=
1
,
000
。
两种方法。第一种是改装的最长不将子序列。我们将每个数和自己应该在的位置的差记录下来，然后就得到一个新的数列d。我们对这个数列做一下最长不将子序列，但是要注意一点，一定要有数可删。什么意思呢，用数学语言描述就是j-i>d[j]-d[i](j>i)，即在i确定的情况下，从i到j之间至少要有d[j]-d[i]个数以保证可以通过删数让j到它自己的位置上。
第二种就是普通的DP。思路、方程、代码详见SephirothLee的《数列》一文，地址 http://www.cnblogs.com/sephirothlee/archive/2010/10/08/1846073.html
参考代码（最长不降子序列）：
1
program
sequence;
2
var
3
n,max,i,j,l:longint;
4
a,d:
array
[
0
..
1001
]
of
longint;
5
f:
array
[
0
..
1001
]
of
longint;
6
ff:boolean;
7
begin
8
readln(n);
9
for
i:
=
1
to
n
do
10
begin
11
read(a[i]);
12
d[i]:
=
i
-
a[i];
//
不能写成i
-
a[i]，否则处理方法不同
13
end
;
14
for
i:
=
n
-
1
downto
1
do
15
for
j:
=
i
+
1
to
n
do
16
if
(d[i]
>=
0
)
and
(d[j]
>=
0
)
and
(d[i]
<=
d[j])
then
//
如果是负数，就不能通过删数归位
17
if
d[j]
-
d[i]
<=
j
-
i
-
1
then
//
关键的限制条件
18
if
(d[i]
<
i)
and
(d[j]
<
j)
then
19
if
f[j]
+
1
>
f[i]
then
f[i]:
=
f[j]
+
1
;
20
ff:
=
false;
21
for
i:
=
1
to
n
do
22
if
max
<
f[i]
then
23
begin
24
ff:
=
true;
25
l:
=
i;
26
max:
=
f[i];
27
end
;
28
if
(d[l]
>
l)
or
(d[l]
<
0
)
then
dec(max);
//
一定要保证第一个数可以归位
29
if
ff
then
writeln(max
+
1
)
//
加上最后面的一个
30
else
writeln(
'
0
'
);
//
如果根本就没有，则输出0
31
end
.
（saltless原创，转载请注明出处）
