现在有一堆石子，一个序列a表示每次可以从石头里拿走多少个石子。当无法再拿出石头的时候，游戏结束。两边都以最佳策略游玩，请问先手者最多能拿走几个石子。
对于这种两边都采取最佳策略的最优解问题，我们可以很轻易的想到博弈DP的模型。通过记忆化搜索，枚举玩家A拿的所有情况，分割成子问题，取最优解即可。因为对手B也会采取最佳策略，所以减去B拿的最优解就是A所得的最优解。
[f[u] = max{(f[u],\; a[i] + (u – a[i]) – f[u – a[i]]), \; a[i] \le u }; ]
建议使用记忆化搜索实现。
int n, k;
int a[105];
int f[10005];
int dfs(int u)
{
if(f[u]) return f[u];
f[u] = 0;
for(int i = 1; i u) break;
f[u] = max(f[u], u - dfs(u - a[i]));
}
return f[u];
}
void solve()
{
cin >> n >> k;
for(int i = 1; i > a[i];
sort(a + 1, a + k + 1);
cout << dfs(n) << '\n';
}
有一圈苹果框，每个框里都有若干苹果（(x=1e18)），现在按顺序循环拿走k个苹果，自动跳过没有苹果的框， 请问最后每个框里还有多少个苹果。
可以想到用二分答案来实现，二分拿苹果的轮数，没有就自动跳过，当拿走的苹果数量
Original: https://www.cnblogs.com/DM11/p/16734283.html
Author: DM11
Title: AtCoder ABC 270 题解(D-F)
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604247/
转载文章受原作者版权保护。转载请注明原作者出处！