Deque 题解

标签：Deque int 题解 sum 3005 dp

题目传送门

一道区间 \(dp\) 题。

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

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

状态的表示

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

\(dp[l][r]\) 表示目前剩下的数为 \(a[l] \thicksim a[r]\) 时，当前取数的人取数所能获得的最大数字和。

状态转移方程

\[dp[l][r]=\max\begin{cases}sum(l,r)-dp[l+1][r]\\ sum(l,r)-dp[l][r-1]\end{cases}\]

边界条件

\[dp[i][i] = a[i]\space (1\le i\le n) \]

答案的表示

\[dp[1][n]-(sum(1,n)-dp[1][n]) \]

最后贴上代码

#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;
}

标签：Deque,int,题解,sum,3005,dp
From： https://www.cnblogs.com/xvl-/p/17062688.html