題意：求最長單調遞減子序列的長度以及有多少種途徑到達該最長單調遞減子序列。
思路：求最長單調遞減子序列是比較容易的了，關鍵是求路徑的條數。而且還要去重。如5 5 2 2 1，其實是只有一條5 2 1。該題難點就在於去重，去重方法如下：
我們在求單調遞減子序列的時候，可以用一個二重for循環求，在循環中dp[i]表示的是到第i個數時的單調遞減子序列的最長長度，我們用如下的for循環求遞減子序列的長度：
[cpp]
for(int j = 0;j < i;++j){
if(num[i] < num[j]){
if(dp[j] > mmax)
mmax = dp[j];
}
}
我們設數組cnt[i]表示有幾種途徑到達第i個數字時的最長長度。則cnt[i]的取值決定於cnt[j](num[j] > num[i] 且 dp[j] == dp[i] - 1 且 j < i)，由於要去重，所以需要倒著循環，這是個比較難想的地方。我就在這裡卡了一天。。。。可以用下面的代碼實現：
[cpp] view plaincopy
CLR(flag,false);
for(int j = i-1;j >= 0 ;--j){
if(num[i] < num[j] ){
if(dp[j] == mmax && !flag[num[j]]){
flag[num[j]] = true;
cnt[i] += cnt[j];
}
}
}
其中的flag數組就是去重的功能，即如果是兩個相同的數都能到達num[i]，則計算一個就可以，且從後計算。
附幾組數據：
5
20 18 25 18 17
輸出：3 2
4
20 15 10 10
輸出：3 1
9
100 96 30 200 196 30 300 296 30
輸出：3 3
5
5 5 2 2 1
輸出：3 1 www.2cto.com
這幾種情況如果都考慮了的話，基本就對了。
代碼：
[cpp]
#include <iostream>
#include <string.h>
#include<cstdio>
using namespace std;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
const int N = 5010;
int dp[N],num[N],sum[N];
bool flag[10*N];
long long cnt[N];
int main(){
//freopen("1.txt","r",stdin);
int n;
while(scanf("%d",&n) != EOF){
for(int i = 0;i < n;++i)
scanf("%d",&num[i]);
CLR(dp,0);
CLR(cnt,0);
CLR(flag,false);
dp[0] = 1;cnt[0]=1;
int mmax = 0;
for(int i = 1;i < n;++i){
mmax = 0;
for(int j = 0;j < i;++j){
if(num[i] < num[j]){
if(dp[j] > mmax)
mmax = dp[j];
}
}
CLR(flag,false);
for(int j = i-1;j >= 0 ;--j){
if(num[i] < num[j] ){
if(dp[j] == mmax && !flag[num[j]]){
flag[num[j]] = true;
cnt[i] += cnt[j];
}
}
}
if(cnt[i] == 0)cnt[i] = 1;
dp[i] = mmax+1;
}
mmax = 0;
for(int i = 0;i < n;++i){
if(mmax < dp[i])
mmax = dp[i];
}
long long ans = 0;
CLR(flag,false);
for(int i = n-1;i >= 0;--i){
if(dp[i] == mmax) {
if(!flag[num[i]]){
ans += cnt[i];
flag[num[i]] = true;
}
}
}
printf("%d %lld\n",mmax,ans);
}
return 0;
}
話說這道題卡了一天多啊，，
10417832 ac_Bool 1952 Wrong Answer C++ 739B 2012-07-10 19:30:37
10429494 ac_Bool 1952 Accepted 296K 125MS C++ 1215B 2012-07-12 08:53:09 wa了8次。。。。
