P1108 低价购买 (DP)

题目

P1108 低价购买

解析

这题做的我身心俱惫，差点自闭。

当我WA了N发后，终于明白了这句话的意思

这题有两问，第一问显然最长严格下降子序列，一看数据范围：5000，跟最长严格上升子序列一样，\(n^2\)直接写就行。

第二问求方案数，方案数也是用dp做

转移方程

//j<i

if (f[i] == f[j] + 1 && a[j] > a[i]) cnt[i] += cnt[j];

这里还要注意一下相同这种情况，

如果对于两个位置\(i,j(j<i)\)来说，

若\(f[i]==f[j]\&\&a[i]==a[j]\)，那就说明到\(i\)与到\(j\)的这两个最长下降子序列是相同的，算一种情况（显然吧应该）。

又因为我们之前把部分算过一次贡献，不再算一遍，那我们就直接不要它了，所以

if (f[i] == f[j] && a[i] == a[j]) cnt[i] = 0;

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, ans, sum;

int a[N], b[N], f[N], cnt[N];

template<class T>inline void read(T &x) {

	x = 0; int f = 0; char ch = getchar();

	while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();

	while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();

	x = f ? -x : x;

	return;

}

int main() {

	read(n);

	for (int i = 1; i <= n; ++i) read(a[i]), b[i] = a[i];

	sort(b + 1, b + 1 + n);

	int len = unique(b + 1, b + 1 + n) - b - 1;

	for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + 1 + len, a[i]) - b;

	for (int i = 1; i <= n; ++i) {

		f[i] = 1;

		for (int j = 1; j <= i; ++j)

			if (a[j] > a[i]) f[i] = max(f[i], f[j] + 1);

	}

	for (int i = 1; i <= n; ++i) ans = max(f[i], ans);

	for (int i = 1; i <= n; ++i) {

		if (f[i] == 1) cnt[i] = 1;

		for (int j = 1; j < i; ++j) {

			if (f[i] == f[j] + 1 && a[j] > a[i]) cnt[i] += cnt[j];

			if (f[i] == f[j] && a[i] == a[j]) cnt[i] = 0;

		}

		if (f[i] == ans) sum += cnt[i];

	}

	printf("%d %d", ans, sum);

	return 0;

}