[原题链接](https://atcoder.jp/contests/abc261/tasks/abc261_d "原题链接") ### 题意 现投掷1枚硬币n次,可能的结果为: 1. value++, money+=x[i]; 2. value=0, money=0; 另,value达到ci时,money+=yi 求投掷n次硬币可能达到的最大money为多少 ### 思路 简单dp,直接来个状态转移 f[i][j]: 当前走到i, 有连续j次正面朝上的money 然后按照第i次正面朝上/朝下,分别转移即可 ```cpp #include #define int long long using namespace std; const int N = 5005; int n, m; int v[N], x[N]; int f[N][N]; //前i次掷骰子的连胜次数为j的最大得分 signed main () { cin >> n >> m; for (int i = 1; i <= n; i ++) cin >> x[i]; for (int i = 1; i <= m; i ++) { int a, b; cin >> a >> b; v[a] = b; } for (int i = 1; i <= n; i ++) { //第i次正面朝上 for (int j = 0; j <= i; j ++) f[i][j] = f[i-1][j-1] + x[i] + v[j]; //第i次正面朝下 //在i次之前所有可能的情况中,记录最大值 for (int j = 0; j < i; j ++) f[i][0] = max (f[i][0], f[i-1][j]); } int ans = 0; for (int i = 0; i <= n; i ++) ans = max (ans, f[n][i]); cout << ans << endl; } //1. value++, money+=x[i]; //2. value=0, money=0; //value达到ci时,money+yi //dp //max (f[n][0], f[n][1],...,f[n][n]); //f[i][j]: 当前走到i, 有连续j次正面朝上的money ``` ### 代码 ```cpp #include using namespace std; typedef long long LL; int n, m; LL f[5005][5005], a[5005], b[5005], ans, maxn; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); LL u, v; for (int i = 1; i <= m; i++) scanf("%lld%lld", &u, &v), b[u] += v; f[1][1] = a[1] + b[1]; for (int i = 2; i <= n; i++) { maxn = 0; for (int j = 1; j <= i; j++) f[i][j] = f[i - 1][j - 1] + a[i] + b[j], maxn = max(f[i - 1][j], maxn); f[i][0] = maxn; } for (int j = 0; j <= n; j++) ans = max(ans, f[n][j]); printf("%lld", ans); return 0; } ```