P2687 [USACO4.3]逢低吸纳Buy Low, Buy Lower 解题报告

秒速五厘米 2021-11-01 07:26 159阅读 0赞

[题目][Link 1]

一道模版题加了个方案计数就蓝了......

## 解题思路 ##

求最优方案直接 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;
    }

转载于:https://www.cnblogs.com/whx666/p/11329651.html

[Link 1]: https://www.luogu.org/problem/P2687