題目地址:

https://codeforces.com/problemset/problem/1738/C

題目的內(nèi)容如下:

Alice and Bob are playing a game on a sequence?a1,a2,…,ana1,a2,…,an?of length?nn. They move in turns and?Alice moves first.

In the turn of each player, he or she should select an integer and remove it from the sequence. The game ends when there is no integer left in the sequence.

Alice wins if the sum of her selected integers is?even; otherwise, Bob wins.

Your task is to determine who will win the game, if both players play optimally.

大概意思是給定一個(gè)序列, Alice和Bob輪流從中取數(shù)直到取完所有數(shù)結(jié)束, 如果Alice取的數(shù)之和為偶數(shù)則勝出，否則Bob勝出，其中Alice先取。

思路

一開始以為是博弈論(直接放棄), 看了題解后才發(fā)現(xiàn)是個(gè)動(dòng)態(tài)規(guī)劃問題。動(dòng)態(tài)規(guī)劃的思路是先將一個(gè)問題轉(zhuǎn)化為子問題， 當(dāng)然這個(gè)問題我們無需構(gòu)造子問題最優(yōu)解，我們只需要找出各個(gè)子問題間的遞推關(guān)系即可。

首先我們要知道奇數(shù)和偶數(shù)的一些性質(zhì)(將偶數(shù)看作為2n, 奇數(shù)看作為2n+1很好證明):

奇數(shù) + 奇數(shù) = 偶數(shù) (偶數(shù)個(gè)奇數(shù)相加為偶數(shù))

偶數(shù) + 偶數(shù) = 偶數(shù) (無論有多少個(gè)偶數(shù)相加結(jié)果仍為偶數(shù))

因此我們先來考慮一些特殊情況:?

證明: 當(dāng)序列全是偶數(shù)時(shí), 那么 Alice 必勝。

無論序列的長度是奇數(shù)還是偶數(shù), Alice最后取得的數(shù)的和一定為偶數(shù), 因此Bob必輸。

證明: 當(dāng)序列全是奇數(shù)時(shí), 如果 Alice 最后能取出偶數(shù)個(gè)奇數(shù), 那么 Alice 必勝, 否則 Bob 勝出。

根據(jù)上述給出的奇數(shù)偶數(shù)的性質(zhì)很任意證明這個(gè)問題，由于 Alice 先取數(shù), 因此 Alice 最后能否取出偶數(shù)個(gè)奇數(shù)是由序列的長度決定的。該問題的解是由奇數(shù)和偶數(shù)的個(gè)數(shù)決定的，我們無無需知道具體的數(shù)字，我們只需要知道奇數(shù)偶數(shù)的個(gè)數(shù)即可。?特例想好了， 那么我們就開始定義dp數(shù)組了:

注意dp數(shù)組的含義, 這是一個(gè)bool類型的數(shù)組,??而dpEven[i][j] 就代表有 i 個(gè)奇數(shù)和 j 個(gè)偶數(shù)情況下先手能否通過最優(yōu)策略得到偶數(shù)和, dp[i][j] 代表有 i 個(gè)奇數(shù)和 j 個(gè)偶數(shù)情況下先手能否通過最優(yōu)策略得到奇數(shù)和。

由于數(shù)據(jù)量較小，我們干脆用"打表"的方式實(shí)現(xiàn)dp 的 base case.

接下來我們來找遞推關(guān)系, 嘗試把所有個(gè)數(shù)的奇數(shù)和偶數(shù)情況下都遍歷出來。

如何進(jìn)行遞推呢, 假設(shè)當(dāng)前為第 n 輪, 我們要分析 Alice 的勝負(fù)態(tài), 我們要把問題轉(zhuǎn)化為第 n - 1 輪 Alice 和 Bob 的勝負(fù)態(tài)。

我們先來考慮 第 n 輪 Alice 贏的情況， 如果奇數(shù)的個(gè)數(shù)是偶數(shù)個(gè),? 在當(dāng)前無論 Alice 拿奇數(shù)或偶數(shù),?在第 n - 1 輪 Bob 想贏必須要先拿到奇數(shù)和勝出。

如果奇數(shù)的個(gè)數(shù)為奇數(shù)個(gè),?那么序列總和為奇數(shù)，第一輪 Alice 先拿一定能拿到偶數(shù)個(gè)數(shù)，那么 Bob就要逼迫 Alice 拿到奇數(shù)和了(想一想例子 [1, 4, 6]，第二種證明方法: 如果 Bob先拿到奇數(shù)和， 那么最后 Alice 一定會(huì)拿到偶數(shù)和，所以想贏只有換一種策略: 拿偶數(shù)和)。?在當(dāng)前無論 Alice 拿奇數(shù)或偶數(shù), 在第 n - 1 輪 Bob 想贏就要逼迫 Alice 拿到奇數(shù)和, 所以在第 n - 1 輪必須要拿到偶數(shù)和勝出。

終于解決了，但還是有一個(gè)問題說是否會(huì)出現(xiàn)平局的情況呢? 也就是Alice用最優(yōu)策略取得的數(shù)的和永遠(yuǎn)為偶數(shù), Bob用最優(yōu)策略取得的數(shù)的和永遠(yuǎn)為奇數(shù)? 實(shí)際上是有的,?比如說[0, 1]就是平局的例子, 只是本題降低了難度, 結(jié)果輸出 Bob 而已。