【P1108 低价购买】题解

2021年11月24日 阅读数:3
这篇文章主要向大家介绍【P1108 低价购买】题解,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

题目连接

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

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

对于 \(i\)\(j\)\(i>j\)),若是 \(a_i=a_j\)\(dp_i=dp_j\),说明他们是相同的,\(i\) 的方案要清0,可是这里不能breakcode

由于对于 \(k\) 知足 \(j<k<i\),咱们 \(i\) 的方案也可能从 \(k\) 转移过了。get

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<bits/stdc++.h>
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<i; ++j)
			if(a[i]<a[j])
				dp[i]=max(dp[i], dp[j]+1);
		if(dp[i]==1) s[i]=1; 
		for(j=1; j<i; ++j) 
		{
			if(dp[j]==dp[i]&&a[i]==a[j]) s[i]=0; 
			else if(a[i]<a[j]&&dp[j]+1==dp[i]) s[i]+=s[j]; 
		}
		cnt=max(cnt, dp[i]); 
		// printf("%lld:%lld %lld\n", i, dp[i], s[i]); 
	}
	for(i=1; i<=n; ++i) 
		if(dp[i]==cnt) ans+=s[i]; 
	printf("%lld %lld\n", cnt, ans); 
	return 0; 
}