????? 一看這道題就想到DP…但是我錯(cuò)誤地認(rèn)為當(dāng)時(shí)的DP思路有后效性，沒(méi)有敢打，最后改裝了一下最長(zhǎng)不降子序列，竟然對(duì)了～
?
【問(wèn)題描述】
雖然msh長(zhǎng)大了，但他還是和喜歡找點(diǎn)游戲自?shī)首詷?lè)。有一天，他在紙上寫(xiě)了一串?dāng)?shù)字：
1
,
1
,
2
,
5
,
4
。
接著他擦掉了一個(gè)1，結(jié)果發(fā)現(xiàn)剩下1,
2
,4都在自己所在的位置上，即1在第1位，2在第2位，4在第4位。
他希望擦掉某些數(shù)后，剩下的數(shù)列中在自己位置上的盡量多。他發(fā)現(xiàn)這個(gè)游戲很好玩，于是開(kāi)始樂(lè)此不
疲地玩起來(lái)……不過(guò)他不能確定最多能有多少個(gè)數(shù)在自己的位置上，所有找到你，請(qǐng)你幫忙計(jì)算一下
!
【輸入格式】
第1行：1個(gè)整數(shù)n，表示數(shù)列的長(zhǎng)度。接下來(lái)一行為n個(gè)空格隔開(kāi)的正整數(shù)，第i行表示Ai。
【輸出格式】
一行一個(gè)整數(shù)，表示擦掉某些數(shù)后，最后剩下的數(shù)列中最多能有多少個(gè)數(shù)在自己的位置上，即Ai
=
i最
多能有多少。
【樣例輸入】
5
1
1
2
5
4
【樣例輸出】
3
【數(shù)據(jù)范圍】
對(duì)于20
%
的數(shù)據(jù)，n
<=
20
；
對(duì)于60
%
的數(shù)據(jù)，n
<=
100
；
對(duì)于100
%
的數(shù)據(jù)，n
<=
1
,
000
。
?
????? 兩種方法。第一種是改裝的最長(zhǎng)不將子序列。我們將每個(gè)數(shù)和自己應(yīng)該在的位置的差記錄下來(lái)，然后就得到一個(gè)新的數(shù)列d。我們對(duì)這個(gè)數(shù)列做一下最長(zhǎng)不將子序列，但是要注意一點(diǎn)，一定要有數(shù)可刪。什么意思呢，用數(shù)學(xué)語(yǔ)言描述就是j-i>d[j]-d[i](j>i)，即在i確定的情況下，從i到j(luò)之間至少要有d[j]-d[i]個(gè)數(shù)以保證可以通過(guò)刪數(shù)讓j到它自己的位置上。
????? 第二種就是普通的DP。思路、方程、代碼詳見(jiàn)SephirothLee的《數(shù)列》一文，地址 http://www.cnblogs.com/sephirothlee/archive/2010/10/08/1846073.html
?
參考代碼（最長(zhǎng)不降子序列）：
?
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];
//
不能寫(xiě)成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
//
如果是負(fù)數(shù)，就不能通過(guò)刪數(shù)歸位
17
if
d[j]
-
d[i]
<=
j
-
i
-
1
then
//
關(guān)鍵的限制條件
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);
//
一定要保證第一個(gè)數(shù)可以歸位
29
if
ff
then
writeln(max
+
1
)
//
加上最后面的一個(gè)
30
else
writeln(
'
0
'
);
//
如果根本就沒(méi)有，則輸出0
31
end
.
（saltless原創(chuàng)，轉(zhuǎn)載請(qǐng)注明出處）
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
