AtCoder-dp_l 题解

发表于2023-03-24更新于2023-05-03

题目传送门

一道区间 dp 题……

在 dp 之前，我们需要明确以下几个东西：

状态的表示，状态转移方程，边界条件跟答案的表示。

状态的表示

定义 sum(l,r)=∑i=lraisum(l,r) = \sum_{i=l}^ra_i

dpl,rdp_{l,r} 表示目前剩下的数为 al∼ara_l \thicksim a_r 时，当前取数的人取数所能获得的最大数字和。

状态转移方程

dpl,r=max⁡{sum(l,r)−dpl+1,rsum(l,r)−dpl,r−1dp_{l,r}=\max\begin{cases}sum(l,r)-dp_{l+1,r}\\ sum(l,r)-dp_{l,r-1}\end{cases}

边界条件

dpi,i=ai (1≤i≤n)dp_{i,i} = a_i\space (1\le i\le n)

答案的表示

dp1,n−(sum(1,n)−dp1,n)dp_{1,n}-(sum(1,n)-dp_{1,n})

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, ans, sum[3005], a[3005], dp[3005][3005];
signed main() {
    ios :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0); // 优化
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i]; // 注意要用前缀和，否则会 TLE
    }
    for (int i = 1; i <= n; i++) dp[i][i] = a[i];
    for (int len = 2; len <= n; len++) {
        for (int l = 1, r = l + len - 1; r <= n; l++, r++) {
            dp[l][r] = max(sum[r] - sum[l - 1] - dp[l + 1][r], sum[r] - sum[l - 1] - dp[l][r - 1]); // 进行 dp
        }
    }
    cout << dp[1][n] - (sum[n] - dp[1][n]);
    return 0;
}