[ABC017D] サプリメント 题解

题目传送门~

一道 DP 前缀和优化好题。

题目分析

首先，朴素 DP 非常好想。可以从后向前考虑，设 \(f_i\) 表示从第 \(i\) 个补品开始的摄取方法数。

摄取一个补品：\(f_i = f_{i+1}\)

摄取两个补品：\(f_i = f_{i+2}\)

以此类推。

则转移方程为：

这里的 \(j\) 指 \(i\) 向后最远能取到的保证不重复的数，这一步可以用 unordered_map 判重。

朴素 DP 参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100005,mod = 1e9+7;
int n,m,a[N],dp[N];
int main()
{
	cin >> n >> m;
	for (int i = 1;i <= n;i++) cin >> a[i];
	dp[n+1] = 1;
	for (int i = n;i >= 1;i--)
	{
		dp[i] = dp[i+1];
		unordered_map<int,bool> mp;//map判重
		mp[a[i]] = 1;
		for (int j = i+1;j <= n;j++)
		{
			if (mp[a[j]]) break;
			dp[i] += dp[j+1] % mod,dp[i] %= mod;
			mp[a[j]] = 1;
		}
	}
	cout << dp[1] << endl;
	return 0;
} 

DP 优化

朴素 DP 时间复杂度 \(O(n^2)\)，于是考虑优化。

朴素 DP 是 \(O(n)\) 枚举查找 \(j\) 的位置，那么可以预处理每个 \(i\) 对应 \(j\) 的位置，再通过前缀和求出 \(f_{i+1} + f_{i+2} + \dots + f_{j}\) 的值，就可以优化状态转移时间复杂度为 \(O(1)\)。

最终复杂度为 \(O(n)\)。

预处理的方法

怎么求出每个 \(i\) 对应的 \(j\) 的位置呢？我们发现 \(j\) 的位置是随着 \(i\) 单调递增的，因为 \(i-1\) 对应的 \(j\) 对于 \(i\) 来说肯定也是可行的。

所以很容易能想到使用双指针算法，时间复杂度 \(O(n)\)。

具体实现见代码。

代码

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

const int N = 100005,mod = 1e9+7;
int n,m,a[N];
int dp[N],bk[N],sum[N];
unordered_map<int,int > mp;	
int main()
{
	cin >> n >> m;
	for (int i = 1;i <= n;i++) cin >> a[i];
	for (int i = 1,j = i;i <= n;i++) //双指针算法
	{
		while (j <= n && !mp[a[j]]) mp[a[j]]++,j++;
		bk[i] = j-1; //存储每个i最远能走到的数
		mp[a[i]]--;
	} 
	dp[n+1] = sum[n+1] = 1;
	for (int i = n;i >= 1;i--)
	{
		//dp[i] = dp[i+1] + dp[i+2] + ... + dp[bk[i] + 1]
		dp[i] =( sum[i+1]-sum[bk[i] + 2] + mod) % mod;
		sum[i] = (sum[i+1] + dp[i]) % mod;
	}
	cout << dp[1] << endl;
	return 0;
}