Problem Summary Given a sequence of N integers, find
the length of the longest decreasing subsequence,
the number of sequences that have this length.
Solution This is clearly a DP problem. Let f[i] be the length of the longest sequence ending at ith number. Then,
f[i] = max{f[j]+1,1} , 1<=j<i && num[i]<num[j]
About subproblem 2, we need to avoid double counting sequences. Let g[i] be the numbers of distinct longest sequences ending at i. If we use
g[i] = 1, if f[i]==1 g[i] = sigma {g[j]} , if 1<=j<i && num[i]<num[j] && f[j]+1==f[i]
to calculate g[i], there will be some redundancy.
If num[i]==num[j] && i<j && f[i]==f[j], then g[j] must include g[i]. That is, sequcences of length f[i] ending at i can also end at j. So for each value, we add in only the count for the most recent occurence.
Code 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std ;
const int maxn = 5002 ;
const int base = 10 ;
int n,price[maxn],f[maxn];
int best_len=0 ;
class BigNumber
{
public :
int len;
int d[200 ];
BigNumber() { len=1 ; d[1 ]=0 ; }
void clear () 1 ; d[1 ]=0 ; }
void print (fstream *fout)
void operator += (const BigNumber &b);
void operator = (const BigNumber &b);
} g[maxn],sum;
void BigNumber::operator += (const BigNumber &b)
{
int l=max(this ->len,b.len),i,tmp,rem;
i=1 ; rem=0 ;
while (i<=l || rem!=0 )
{
tmp=rem;
if (i<=this ->len) tmp+=this ->d[i];
if (i<=b.len) tmp+=b.d[i];
this ->d[i]=tmp%base;
rem=tmp/base;
i++;
}
if (i-1 >this ->len) this ->len=i-1 ;
}
void BigNumber::operator = (const BigNumber &b)
{
this ->len=b.len;
for (int i=1 ;i<=b.len;i++)
this ->d[i]=b.d[i];
}
void BigNumber::print(fstream *fout)
{
for (int i=len;i>=1 ;i--)
*fout<<d[i];
*fout<<endl ;
}
int main ()
{
fstream fin ("buylow.in" ,ios::in) ;
fstream fout ("buylow.out" ,ios::out) ;
fin>>n;
for (int i=1 ;i<=n;i++)
fin>>price[i];
for (int i=1 ;i<=n;i++)
{
f[i]=1 ;
for (int j=i-1 ;j>=1 ;j--)
if (price[j]>price[i] && f[j]+1 >f[i])
f[i]=f[j]+1 ;
if (f[i]>best_len) best_len=f[i];
}
for (int i=1 ;i<=n;i++)
{
if (f[i]==1 )
g[i].len=g[i].d[1 ]=1 ;
else
{
g[i].clear();
int goal = f[i]-1 ;
int last = -1 ;
for (int j=i-1 ;j>=1 ;j--)
if (price[j]>price[i] && f[j]==goal && price[j]!=last)
{
g[i]+=g[j];
last=price[j];
}
}
}
int last = -1 ;
sum.clear();
for (int i=n;i>=1 ;i--)
if (f[i]==best_len && price[i]!=last)
{
sum+=g[i];
last=price[i];
}
fout<<best_len<<" " ;
sum.print(&fout);
fin.close();
fout.close();
return 0 ;
}