洛谷 P1108 分析（别看）

科技起源

2026-07-09 15:01:22

发布于：河北

2阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最大值和一个方案数

1.2 题目背景、允许、禁止与限制

背景：有一个 $n$ 个数字组成的股票序列，每天选择的股票价格不应大于等于上次购买股票的价格
允许：求最多能买多少支股票以及购买这种数量股票的方案数
禁止：
限制：这里的两种方案只要“看起来一样”就算一样，也就是序列 $[4,3,3,2,1]$ 中选择下标 $1,2,4,5$ 和选择下标 $1,3,4,5$ 是一样的方案

1.3 题目数据范围与猜测

$1 \le n \le 5000 \longrightarrow O(n^2)$

1.4 一句话概括题意

有一个数字序列 $a$ ，求其最长下降子序列长度以及构成此答案方案数

2 题目破题推导

注：以下七种方法都可以考虑一下
这道题最长下降子序列就不用考虑了，非常简单的 $O(n^2)$ 方法，接下来我们讨论的是“方案数”

2.1 大拆小、小组大

2.2 正向思维转逆向思维，逆向思维转正向思维

2.3 分情况考虑

首先，正常情况讲，dp数组的定义是：考虑并选择第 $i$ 天，最多能买的次数
然后我们就必须要引入这个想法：f数组的定义：以第 $i$ 天为结尾，刚好到达 $dp_i$ 的这种最多购买次数的不重复方案数有多少种。
那我们就分情况考虑：
首先，要确保下降，就要保证 $a_j>a_i$

如果 $dp_i<dp_j+1$ ，就代表我找到了更长的方案。那原来的所有方案都要废弃，把 $f_i$ 变成 $f_j$
如果 $dp_i=dp_j+1$ ，就代表选第 $j$ 天为结尾仍然是最优方案，那我就要把选第 $j$ 天的所有可能的方案数都累加进来，也就是 $f_i=f_i+f_j$
- 但是题目中要求“不重复方案”，因此需要额外判断去重：如果 $a_i=a_j$ ，说明到这两次选的一定是一样的，那就直接清空 $f_j$ ，这样后续就选不了了

2.4 数学

2.5 以终为始、以始为终

2.6 手动推导

2.7 边界测试

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：最长下降子序列，动态求取方案数 $\longrightarrow$ $\huge{线性动态规划、计数动态规划}$

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

int n;
const int N = 5555;
int a[N];
int dp[N], f[N];

int main(){
	
	cin >> n;
	for (int i = 1;i <= n;i++){
		cin >> a[i];
		f[i] = 1;
		dp[i] = 1;
	}
	for (int i = 2;i <= n;i++){
		for (int j = 1;j < i;j++){
			if (a[j] > a[i]){
				if (dp[i] < dp[j] + 1){// 原来接的不是最长下降子序列 
					dp[i] = dp[j] + 1;
					f[i] = f[j];
				} else if (dp[i] == dp[j] + 1){// 接那几个都是最长下降子序列 
					f[i] += f[j];
				}
			}
			if (a[j] == a[i]) {
				f[j] = 0;
			}
	    }
	}
	int mx = INT_MIN;
	for (int i = 1;i <= n;i++){
		mx = max(mx, dp[i]);
	}
	int sum = 0;
	for (int i = 1;i <= n;i++){
		if (dp[i] == mx){
			sum += f[i];
		}
	}
	cout << mx << " " << sum;
	
	return 0;
}