一道模版题加了个方案计数就蓝了......
求最优方案直接 n2 不多说，记录方案数还需要一点小技巧
高精直接用double水了（懒）......
f[i] 表示前 i 个数的最优方案，num[i] 表示前 i 个数的最优方案数
当循环到第 i 个时，先照常算出f[i] 和 num[i]，然后枚举 0——i-1 的数 (j)，如果a[j] = a[i] 相等并且 f[i] = f[j]，说明前 j 个数的最优方案数num[j]都已经包括在num[i]里了；
这时有两种处理方案避免重复：
1、把 num[j] 赋值为0；
2、把 num[i] 的值减去 num[j]；
这两种方法都可以（代码里写的第一种）
做完后枚举 i 找到最优解，注意：统计方案时要把所有 f[i] = 最优解的 num[i] 都加上
#include <bits/stdc++.h>
using namespace std;
inline void read (long long &x) {
char ch = getchar ();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
}
long long n, a[5038], f[5038], w;
double num[5038], sum;
int main() {
read (n);
for (int i = 1; i <= n; ++i) read (a[i]);
a[0] = INT_MAX, num[0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j)
if (a[i] < a[j] and f[j] + 1 > f[i]) f[i] = f[j] + 1, num[i] = num[j];
else if (a[i] < a[j] and f[j] + 1 == f[i]) num[i] += num[j];
for (int j = 0; j < i; ++j) if (a[j] == a[i] and f[j] == f[i]) num[j] = 0;
}
for (int i = 1; i <= n; i++) if (f[i] > f[w]) w = i;
for (int i = 1; i <= n; i++) if (f[i] == f[w]) sum += num[i];
printf ("%lld %.0lf", f[w], sum);
return 0;
}
P2687 [USACO4.3]逢低吸纳Buy Low, Buy Lower 解题报告
原文：https://www.cnblogs.com/whx666/p/11329651.html