二维dp的详细题解

用二维DP来写，其中 dp[i][k] 表示在第 $i$ 次投掷后，连续正面次数为 $k$ 时的最大金额。
定义：

dp[i][k]：在第 $i$ 次投掷后，连续正面次数为 $k$ 时的最大金额。
$i$ 从1到 $N$，$k$ 从0到 $i$（因为最多连续 $i$ 次正面）。

初始化：

对于 $i=1$：

如果选择反面：（$k=0$）：dp[1][0] = 0，因为没有前面的金额。
如果选择正面：（$k=1$）：dp[1][1] = X[1] + mp[1]，因为计数器为1，可能有奖金。

状态转移：

对于每个 $i$ 从2到 $N$：

选择反面（$k=0$）：dp[i][0] = 前一步所有状态的最大值，即 max(dp[i-1][j]) for $j=0$ to $i-1$，因为选择反面不增加金额，计数器重置为0。
选择正面（$k \geq 1$）：为了有 $k$ 次连续正面，必须前一次有 $k-1$ 次连续正面，即从 dp[i-1][k-1] 转移：

dp[i][k] = dp[i-1][k-1] + X[i] +mp[k]。
这里，mp[k] 是当计数器达到 $k$ 时可能的奖金。

#include <bits/stdc++.h>
using namespace std;
#define V vector
#define all0(x) (x).begin(),(x).end()
#define all1(x) (x).begin()+1,(x).end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
typedef long long LL;
typedef pair<int, int> pi;
typedef pair<LL, LL> pl;
const int N = 5000 + 20;
const int INF = 0x3f3f3f3f;
const LL INFLL =0x3f3f3f3f3f3f3f3f;
int n , m;
LL x[N] , c[N] , y[N];
LL dp[N][N]; // dp[i][j] 表示为在投第i次并且连续正面次数为j时,能获得的最大价值
map<LL ,LL > mp;
void so() {
		cin >> n >> m;
		for(int i = 1; i <= n ; i++ ) cin >> x[i];
		for(int i = 1 ; i <= m ; i++ ) cin >> c[i] >> y[i] , mp[c[i]] = y[i];
		dp[1][1] = mp[1] + x[1];//初始化
		for(int i = 2 ; i <= n ; i++ ){
			dp[i][0] = max(dp[i][0] , dp[i - 1][0]);//因为下面k从1开始，所以计算i - 1 ，0时的最大值
			for(int k = 1 ; k <= i ; k++){
				dp[i][0] = max(dp[i - 1][k] , dp[i][0]); //取最大值.
				dp[i][k] = max(dp[i][k] , dp[i - 1][k - 1] + mp[k] + x[i]);//状态转移
			}
		}
		LL ans = 0;
		for(int i = 0 ; i <= n ; i++) ans = max(ans , dp[n][i]);
		cout <<ans;
}
int main() {
    IOS
    int tt=1;
  //  cin >> tt;
    while (tt--)
    so();
}