P1108 低价购买
斯德哥尔摩
2018-10-20 21:38:51
[P1108 低价购买](https://www.luogu.org/problemnew/show/P1108)
第一问显然直接$O(n^2)$跑$\text{类}LIS$即可。
第二问直接在第一问求出的$dp[i]$的基础上计数即可。
但是！要去重。。。
也就是不能有两个数列是相同的。。。
为了这个坑点我还$WA\times1$。。。
这样下去吃枣药丸。。。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 5010
using namespace std;
int n,maxn=0;
long long ans=0;
int val[MAXN],dp[MAXN],num[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void work(){
for(int i=1;i<=n;i++){
num[i]=0;
if(dp[i]==1)num[i]=1;
for(int j=1;j<i;j++){//递推+判重
if(val[j]>val[i]&&dp[i]==dp[j]+1)num[i]+=num[j];
else if(dp[i]==dp[j]&&val[i]==val[j])num[i]=0;
}
if(dp[i]==maxn)ans+=num[i];
}
printf("%lld\n",ans);
}
void init(){
n=read();
for(int i=1;i<=n;i++){
val[i]=read();
dp[i]=1;
for(int j=1;j<i;j++)if(val[j]>val[i])dp[i]=max(dp[i],dp[j]+1);
maxn=max(maxn,dp[i]);
}
printf("%d ",maxn);
}
int main(){
init();
work();
return 0;
}
```