LightOJ 1031 - Easy Game（概率）

本文主要是介绍LightOJ 1031 - Easy Game（概率），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：LightOJ 1031 - Easy Game

代码

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int maxn = 105;int N, A[maxn], S[maxn], dp[maxn][maxn];
bool vis[maxn][maxn];void init () {scanf("%d", &N);for (int i = 1; i <= N; i++) scanf("%d", &A[i]);S[0] = 0;for (int i = 1; i <= N; i++) S[i] = S[i-1] + A[i];memset(vis, false, sizeof(vis));
}int solve (int l, int r) {int& ret = dp[l][r];if (vis[l][r]) return ret;vis[l][r] = true;int sum = ret = S[r] - S[l-1];for (int i = l; i < r; i++) {int ls = solve(l, i);int rs = solve(i+1, r);ret = max(sum - min(ls, rs), ret);}return ret;
}int main () {int cas;scanf("%d", &cas);for (int kcas = 1; kcas <= cas; kcas++) {init();int ans = solve(1, N);int ret = S[N] - ans;printf("Case %d: %d\n", kcas, ans - ret);}return 0;
}

这篇关于LightOJ 1031 - Easy Game（概率）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---