?
題目出處： http://acm.hdu.edu.cn/showproblem.php?pid=5064
題意： 給定n個數(shù)，求滿足以下兩個條件的子序列的最大長度：
?。?）C 1 <C 2 <C 3 <......<C t ;
?。?）C 2 -C 1 <C 3 -C 2 <......<C t -C t-1 .
?
分析： 解結(jié)構(gòu)一定為為N 1 ，N 1 ，N 1 ，......，N 1 ，N 2 ，N 3 ，......，N t ?
??設(shè)dp[i][j]表示以num[i], num[j]結(jié)尾的有效序列的長度，則有
? ? ? ? ?dp[i][j] = max(dp[k][i]+ 1) ,,,,,,,k<=i且num[i]-num[k]<=num[j]-num[i]
?
剪枝一：
? ? ? ? ? ? ?考慮非遞減序列 num[s]，num[k]，num[i]，num[j] ，num[e]，
? ? ? ? ? ? ?容易得到 dp[s][i]<=dp[s][i] （例如1,2,3） 即右端點固定 左端點越遠越小，
? ? ? ? ? ? ?同時因為序列從小到大排列，因此 左端點越遠num[i]-num[k]越大，
? ? ? ? ? ? ?所以，對于算某一特定的dp[i][j]時num[j]-num[i]是一個定值從k=i開始遞減遍歷dp[k][i]+ 1 取最大值，待條件不滿足時跳出循環(huán)。
? ? ? ?
剪枝二：
? ? ? ? ? ? ?因為 若num[i]-num[k]<=num[j]-num[i]成立 則num[i]-num[k]<=num[j+1]-num[i]必成立，
? ? ? ? ? ? ?即 dp[i][j]<=dp[i][j+1] （例如 1(num[k])，4(num[i])，5(num[j])，8(num[j+1])）
? ? ? ? ? ? ?即 左端點固定 小區(qū)間能取到的序列 大區(qū)間一定可以取到，
? ? ? ? ? ? ?所以，每次計算新的dp[i][j]時k只要在上次的基礎(chǔ)上繼續(xù)向左遍歷dp[k][i]+ 1，取最大值即可。
?
源代碼：
1
#include<cstdio>
2
#include<iostream>
3
#include<map>
4
using
namespace
std;
5
int
n,M,num[
3000
],cnt[
3000
],size,dp[
3000
][
3000
];
6
7
int
maxVal(
int
a,
int
b){
return
a>b?
a:b;}
8
9
int
main()
10
{
11
int
t;
12
scanf(
"
%d
"
,&
t);
13
while
(t--
)
14
{
15
scanf(
"
%d%d
"
,&n,&
M);
16
int
i,j,k;
17
size =
0
;
//
序列中有size個不同的數(shù)
18
map<
int
,
int
>
mp;
19
map<
int
,
int
>
::iterator it;
20
//
記錄序列中某個數(shù)i出現(xiàn)了幾次,
21
for
(i=
0
;i<n;i++
)
22
{
23
int
a;
24
scanf(
"
%d
"
,&
a);
25
mp[a]++
;
26
}
27
//
用map是可以默認取數(shù)據(jù)時從小到大
28
//
PS：網(wǎng)絡(luò)上不用map用數(shù)組預(yù)先處理的執(zhí)行時間約600MS，用map約200MS
29
for
(it=mp.begin(); it!=mp.end();it++
)
30
{
31
num[size] = it->
first;
32
cnt[size] = it->
second;
33
size++
;
34
}
35
36
int
res =
1
;
37
for
(i=
0
;i<size;i++
)
38
{
39
dp[i][i] =
cnt[i];
40
res =
maxVal(res, dp[i][i]);
41
k=
i;
42
int
temp = -
1
;
43
for
(j=i+
1
;j<size;j++
)
44
{
45
for
(;k>=
0
;k--
)
46
{
47
if
(num[i]-num[k]<=num[j]-
num[i])
48
{
49
temp = maxVal(dp[k][i] +
1
,temp);
50
}
51
else
52
{
53
break
;
54
}
55
}
56
dp[i][j] =
temp;
57
res =
maxVal(res, dp[i][j]);
58
}
59
}
60
printf(
"
%d\n
"
,res);
61
62
}
63
return
0
;
64
}
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
