【P1108 低价购买】题解

题目链接

首先第一问很好求，就是求最长下降子序列，\(n\leqslant 5000\)，\(O(n^2)\) 暴力转移就行。

而这道题的难点就在于去重。

对于 \(i\) 和 \(j\)（\(i>j\)），如果 \(a_i=a_j\) 且 \(dp_i=dp_j\)，说明他们是相同的，\(i\) 的方案要清0，但是这里不能break！

因为对于 \(k\) 满足 \(j，我们 \(i\) 的方案也可能从 \(k\) 转移过了。

Code

// Problem: P1108 低价购买
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1108
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define M
//#define mo
#define N 5010
int n, m, i, j, k; 
int dp[N], s[N], a[N]; 
int cnt, ans; 

signed main()
{
//	freopen("tiaoshi.in", "r", stdin); 
//	freopen("tiaoshi.out", "w", stdout); 
	n=read(); 
	for(i=1; i<=n; ++i)
	{
		a[i]=read(); 
		dp[i]=1; 
		for(j=1; j