Bricks Game（HackerRank play-game）

https://vjudge.net/problem/HackerRank-play-game 有n个数，位置固定 玩家a和玩家b玩一个游戏，序号从小到大拿这n个数 两人循环，每人每次可以拿1/2/3个数，直到全部拿完， 每次都是a先手 问最后a拿到的数之和最大是多少 dp[i] 表示玩家在第i个数进行决策时，所能拿到的和的最大值 sum[i] 表示 a[i]+a[i+1]+....+a[n] 状态方程： dp[i] = max (sum[i] - dp[i+1],  sum[i] - dp[i+2], sum[i] - dp[i+3] ) 第1个数的所能得到的最大值由后面的状态得到

所以 从后往前 dp

#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <queue> #include <vector> #include <cmath> #include <stack> #include <string> #include <sstream> #include <map> #include <set> #define pi acos(-1.0) #define LL long long #define ULL unsigned long long #define inf 0x3f3f3f3f #define INF 1e18 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; typedef pair<int, int> P; const double eps = 1e-10; const int maxn = 1e6 + 5; const int N = 1e4 + 5; const int mod = 1e8; LL dp[maxn]; int n; LL a[maxn]; LL sum[maxn]; int main(void) { std::ios::sync_with_stdio(false); // freopen("in.txt", "r", stdin); int T; cin >> T; while (T--) { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; sum[n+1] = 0; for (int i = n; i >= 1; i--) sum[i] = sum[i+1] + a[i]; if (n <= 3){ cout << sum[1] << endl; continue; } // 从后面的状态 得到前面的状态 dp[n] = a[n]; dp[n-1] = dp[n] + a[n-1]; dp[n-2] = dp[n-1] + a[n-2]; for (int i = n-3; i >= 1; i--){ dp[i] = max(sum[i] - dp[i+1], max(sum[i] - dp[i+2], sum[i] - dp[i+3])); } cout << dp[1] << endl; } return 0; }