商城网站设计公司有哪些,个人网站上线流程,网站开发和app开发的区别,wordpress调用登录logo一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
731E - Funny Game 二、解题报告
1、思路分析
游戏规则其实就是交替取前缀和
考虑 f(i) 为 某人先手取前 i 个#xff0c;最终能得到的最大分差
由于每人都是最佳发挥#xff0c;所以有如下状态转移最终能得到的最大分差
由于每人都是最佳发挥所以有如下状态转移
f(i) acc[i] - max(f(j))i 1 j n
为什么呢
假如A得分为sumAB得分为sumB
计算f(i) 时候 f(i) sumA - sumB
那么转移的时候 f(j) sumB’ - sumA‘
要f(i) - f(j) sumA - sumB
2、复杂度 时间复杂度 O(N)空间复杂度O(N) 3、代码详解
#include bits/stdc.h
// #include ranges
// #define DEBUG
using i64 long long;
using u32 unsigned;
using u64 unsigned long long;
constexpr int inf32 1E9 7;
constexpr i64 inf64 1E18 7;
constexpr double eps 1E-9;void solve() {int n;std::cin n;std::vectorint acc(n);for (int i 0; i n; i) {std::cin acc[i];;if (i)acc[i] acc[i - 1];}for (int i n - 2; i; -- i) {acc[i] std::max(acc[i 1], acc[i] - acc[i 1]);}std::cout acc[1];
}auto FIO []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
} ();int main() {#ifdef DEBUGfreopen(in.txt, r, stdin);freopen(out.txt, w, stdout);#endif int t 1;// std::cin t;while (t --)solve();return 0;
}
