????? 一看這道題就想到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原創，轉載請注明出處）
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
