本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-26 15:33:17

看一眼题目， 就能发现是一道裸 dp 题。
既然是 dp， 那就三步走起：

第 1 步： 设状态

下面的 $n$，$a_i$ 如题所述， 我们将连击 $i$ 次得到的奖励设为 $cc_i$，$dp_{i,j}$ 为在第 $i$ 时刻连击 $j$ 次能够得到的最大分数， 初始时设 $dp_{1,0}$ 为 $0$。
这样最后的答案就是 $\max(dp_{n,j})(1\le j\le n)$。

第 2 步： 设状态转移方程

根据题意， 在第 $i$ 时刻， 若不点击，那么 $dp_{i,0}$ 就等于：
$$dp_{i,0}=\max(dp_{i-1,k})(1\le k\le n)$$ 那若点击， 即 $j\ne 0$， 那么 $dp_{i,j}$ 就等于：
$$dp_{i,j}=dp_{i-1,j-1}+a_i+cc_j$$ 写在一起就是：
$$dp_{i,j}=\begin{cases}\max(dp_{i-1,k})(1\le k\le n)&(j=0)\\dp_{i-1,j-1}+a_i+cc_j&(j\ne 0)\end{cases}$$ 思路有了， 实现还会远吗？

第 3 步： 写代码

写的时候， 我们发现这道题与其他题一样， 第一维也是可以压掉的， 只需要开个变量暂存最大值， 循环方向从顺序改为逆序即可。
代码：

#include<bits\/stdc++.h>
using namespace std;
long long n,m,a[5005],b,c,dp[5005],cc[5005],ans;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++){
		cin>>b>>c;
		cc[b]=c;
	}
	for(int i=1;i<=n;i++){
		long long maxn=0;
		for(int j=1;j<=i;j++) maxn=max(maxn,dp[j]);
		for(int step=i;step>=1;step--) dp[step]=dp[step-1]+a[i]+cc[step];
		dp[0]=maxn;
	}
	for(int step=1;step<=n;step++) ans=max(ans,dp[step]);
	cout<<ans;
	return 0;
}