B-Game
https://tioj.ck.tp.edu.tw/problems/1553
Description
B-Game是個殘酷的兩人卡片對戰遊戲(Battle Game)
檯面上有$n$張卡片，排成環狀，每張卡片有其數值
兩人輪流取卡片，只能選與已經取過的卡片相鄰的卡片，但第一個人不受此限
選完卡片之後，勝負決定在將兩人手中卡片的數值和
若某位玩家得分大於另一位玩家，無論大多少均是勝利
輸出一行包含兩個數
分別是一開始有幾種拿法可以讓先拿的人勝利
與先拿的人最多可以拿到多少
Solution
一開始我沒有注意到環型的條件，送了好多次假解XD
後面還忘記%n，WA到癱軟www
現在假設先手第一步取了某張卡
則剩下的卡片就是環上的一段連續區間，並且不管怎麼拿都會一直保持是連續區間
可以透過奇偶性知道最後一步輪到誰拿，且拿的位置肯定是區間的最左邊或是最右邊
而對手ㄧ定會讓自己分數最低，我們則是讓分數盡量高
因此可以列出簡單的2D/0D轉移式，得到每個區間可以從兩頭拿時先手的最高得分
再加上先手第一步取得的分數就可以知道從每個地方起手先手所能得到的最高分
也就知道在那個位置是否有機會勝利了
AC code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <cstdio>
inline int min(int a, int b) {return a<b?a:b;}
inline int max(int a, int b) {return a>b?a:b;}
const int N = 225;
int n, v[N], dp[N][N], sum, cnt, mx = 0;
signed main() {
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", v+i);
for(int i = 0; i < n; i++) sum += v[i];
for(int L = 1; L <= n-1; L++) {
for(int i = 0; i < n; i++) {
if(n-L & 1) {
dp[i][L] = min(dp[i][L-1], dp[(i+1)%n][L-1]);
}else {
dp[i][L] = max(dp[i][L-1]+v[(i+L-1)%n], dp[(i+1)%n][L-1]+v[i]);
}
//cout << dp[i][L] << ' ';
}
//cout << '\n';
}
//for(int i = 0; i < n; i++) cout << v[i]+dp[(i+1)%n][n-1] << ' '; cout << '\n';
//debug(sum);
for(int i = 0; i < n; i++) {
int t = v[i]+dp[(i+1)%n][n-1];
if(t > mx) mx = t;
if(t > sum-t) ++cnt;
}
printf("%d %d\n", cnt, mx);
}
|