题面
给你一个长度为n的序列，求这个序列的最长下降子序列的长度以及方案数。1<=n<=5000
链接：http://poj.org/problem?id=1952
思路
很容易想到一个状态(f_i,_j)表示以(a_i)时，长度为j的方案数。
转移方程：(f_i,_j)=(egin{matrix} sum_{k=j-1\,and\,a_k>a_i}^{i-1} end{matrix} f_k,_{j-1})
但很明显，这是O((n^3)),会超时。dp有一个很常用的优化就是舍去冗余状态，我们考虑对于到i为止的最长下降子序列，它只可能由到k(1<=k<j (a_k) (a_i))为止的最长的序列转移过来，我们所要求的，和要知道的都是最长的，所以(f_i,_j)的第二维完全可以去掉，但同时我们还是需要知道长度，所以我们设(f_i)表示以(a_i)结尾的最长下降子序列的方案数，(g_i)表示以(a_i)结尾的最长下降子序列的长度。假设原序列的数两两不同，则有转移方程：
(f_i=egin{matrix} sum_{k=1\,and\,g_k=g_i-1}^{i-1} end{matrix} f_k)
那现在数可能相同，我们考虑对于(a_k)=(a_j)>(a_i),k<j<i，(f_k)的范围被(f_j)包含，所以如果(g_k)=(g_j)，那么f_k的方案数一定被包含在了f_j中，所以我们只要用f_j来转移f_i就可以啦，即对于所有相等的(a_k),k<i，我们只需要用最大的k来更新f_i就可以了，具体操作，可以倒序循环，扫到一个之前没有扫过的(a_k)的值，就做一个标记，以后再扫到时就跳过。在最后求最终答案时也要注意这一点。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=5e3+10;
typedef long long ll;
ll f[N];
int g[N],a[N],vis[(1<<16)+10];
int main()
{
int n,ans=0;
ll cnt=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
g[i]=f[i]=1;
for(int j=i-1;j>=1;j--)
{
if(!vis[a[j]])
{
vis[a[j]]=1;
if(a[j]<=a[i]||g[j]+1<g[i]) continue;
if(g[j]+1>g[i]) g[i]=g[j]+1,f[i]=0;
f[i]+=f[j];
}
}
memset(vis,0,sizeof(vis));
}
for(int i=n;i>=1;i--)
{
if(g[i]>ans) ans=g[i],cnt=0;
if(!vis[a[i]]&&g[i]==ans) cnt+=f[i];
vis[a[i]]=1;
}
printf("%d %lld
",ans,cnt);
return 0;
}