POJ 1952 Buy Low，Buy Lower

題目大意：

求最長下降子序列及其個數（嚴格的…..）

分析：

求最長上升子序列很簡單大家都會，那麼方案數呢？？記得之前做過一道題求的是最短路的計數，那道題是在更新最短路徑時更新其對應方案數，這道題是不是也可以這樣做呢？是以我們定義num[i]代表前i個數中最長子序列的個數，如果f[i]=f[j]+1(i>j)就代表i可以由j轉移而來，是以j的方案數目包含在i中，那麼num[i]=num[i]+num[j]。有了怎麼轉移，我們還要考慮一個嚴肅的問題，怎麼去重？？

看下面一段代碼：

for(int i=;i<=n;i++)
        for(int j=i-;j>=;j--){
            if(f[i]==f[j]+&&a[j]>a[i])
                num[i]+=num[j];
            if(a[i]==a[j]){
                if(f[i]==) 
                    num[i]=;
                break;
            }
        }
           

這是什麼意思呢？？Ｏ(≧口≦)Ｏ

我們還是規定i>j，如果a[i]=a[j]（因為我們是倒着往前找的）就代表我們不需要再往前枚舉更新方案數目了，因為j之前的方案數目已經包含在j中了，而如果f[i]=1這代表什麼呢？？代表i前面沒有比它大的數，那麼顯然f[j]也應該等于1，就是說ij方案數完全相同，這麼來說如果我們保留i的方案數目，那麼就會和j重複，而又因為i在j的後面是以我們顯然是要保留j而把i的方案數目清零

代碼如下：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=+;
int n,a[maxn],f[maxn],num[maxn];
inline int read(){
    char ch=getchar();
    int f=,x=;
    while(!(ch>='0'&&ch<='9')){
        if(ch=='-')
            f=-;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
        x=x*+ch-'0',ch=getchar();
    return f*x;
}
signed main(void){
    n=read();
    for(int i=;i<=n;i++)
        a[i]=read(),f[i]=,num[i]=;
    for(int i=;i<=n;i++)
        for(int j=;j<i;j++)
            if(a[i]<a[j])
                f[i]=max(f[i],f[j]+);
    for(int i=;i<=n;i++)
        if(f[i]==)
            num[i]=;
    for(int i=;i<=n;i++)
        for(int j=i-;j>=;j--){
            if(f[i]==f[j]+&&a[j]>a[i])
                num[i]+=num[j];
            if(a[i]==a[j]){
                if(f[i]==) 
                    num[i]=;
                break;
            }
        }
    int mx=,ans=;
    for(int i=;i<=n;i++)
        mx=max(mx,f[i]);
    for(int i=;i<=n;i++)
        if(f[i]==mx)
            ans+=num[i];
    cout<<mx<<" "<<ans<<endl;
    return ;
}
           

by >o< neighthorn