P1：機械鼠
有 n 個位置上有食物，老鼠一開始在位置 x (-100~100)，可以決定今天要往左還是往右，求最多能吃幾個、最後位置。
ZeroJudge 連結
解法：-100~100 → 0~200
#include <iostream>
using namespace std;
int main(){
int x, n, temp;
bool a[201] = {false};
cin >> x >> n;
x += 100;
while(n--){
cin >> temp;
a[temp + 100] = true;
}
int l = 0, r = 0, maxL, maxR;
for(int i=x; i>=0; i--){
if(a[i]) l++, maxL = i;
}
for(int i=x; i<201; i++){
if(a[i]) r++, maxR = i;
}
if(l > r) cout << l << ' ' << maxL - 100 << '\n';
else cout << r << ' ' << maxR - 100 << '\n';
}P2：卡牌遊戲
在 n * m 的表格中，你可以消除兩個之間沒有障礙物的相同數值，求最大分數。
ZeroJudge 連結
解法：模擬題，先水平做，再垂直做。
#include <iostream>
using namespace std;
int main(){
int n, m, ans = 0;
cin >> n >> m;
int a[n][m];
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin >> a[i][j];
}
}
bool update = true;
while(update){
update = false;
for(int i=0; i<n; i++){
for(int j=0; j<m-1; j++){
if(a[i][j] == -1) continue;
int now = j + 1;
while(a[i][now] == -1){
now++;
if(now >= m){
now = -1;
break;
}
}
if(now != -1 && a[i][j] == a[i][now]){
update = true;
ans += a[i][j];
a[i][j] = -1;
a[i][now] = -1;
}
}
}
for(int i=0; i<m; i++){
for(int j=0; j<n-1; j++){
if(a[j][i] == -1) continue;
int now = j + 1;
while(a[now][i] == -1){
now++;
if(now >= n){
now = -1;
break;
}
}
if(now != -1 && a[j][i] == a[now][i]){
update = true;
ans += a[j][i];
a[j][i] = -1;
a[now][i] = -1;
}
}
}
}
cout << ans << '\n';
}P3：搬家
在 n * m 的字元矩陣中，有不同的水管開口方向，求最大連通塊的大小。
ZeroJudge 連結
解法：BFS。(用 DFS 只會拿到 95 分，因為會遞迴過深導致 Stack Overflow)
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int n, m;
char a[500][500];
bool visited[500][500];
int f(int i, int j){
int count = 1;
queue<pair<int, int>> q;
q.push({i, j});
visited[i][j] = true;
while(!q.empty()){
int x = q.front().first, y = q.front().second;
q.pop();
if(a[x][y] == 'X' || a[x][y] == 'I' || a[x][y] == 'L' || a[x][y] == 'J'){ // 上面接東西
if(x-1 >= 0 && !visited[x-1][y] && (a[x-1][y] == 'X' || a[x-1][y] == 'I' || a[x-1][y] == '7' || a[x-1][y] == 'F')){
count++, q.push({x-1, y}), visited[x-1][y] = true;
}
}
if(a[x][y] == 'X' || a[x][y] == 'I' || a[x][y] == '7' || a[x][y] == 'F'){ // 下面接東西
if(x+1 < n && !visited[x+1][y] && (a[x+1][y] == 'X' || a[x+1][y] == 'I' || a[x+1][y] == 'L' || a[x+1][y] == 'J')){
count++, q.push({x+1, y}), visited[x+1][y] = true;
}
}
if(a[x][y] == 'X' || a[x][y] == 'H' || a[x][y] == '7' || a[x][y] == 'J'){ // 左邊接東西
if(y-1 >= 0 && !visited[x][y-1] && (a[x][y-1] == 'X' || a[x][y-1] == 'H' || a[x][y-1] == 'L' || a[x][y-1] == 'F')){
count++, q.push({x, y-1}), visited[x][y-1] = true;
}
}
if(a[x][y] == 'X' || a[x][y] == 'H' || a[x][y] == 'L' || a[x][y] == 'F'){ // 右邊接東西
if(y+1 < m && !visited[x][y+1] && (a[x][y+1] == 'X' || a[x][y+1] == 'H' || a[x][y+1] == '7' || a[x][y+1] == 'J')){
count++, q.push({x, y+1}), visited[x][y+1] = true;
}
}
}
return count;
}
int main(){
string s;
cin >> n >> m;
for(int i=0; i<n; i++){
cin >> s;
for(int j=0; j<m; j++){
a[i][j] = s[j];
}
}
int ans = -1;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(a[i][j] != '0' && !visited[i][j]){
ans = max(ans, f(i, j));
}
}
}
cout << ans << '\n';
}P4：投資遊戲
長度為 n 的陣列(每天的收益)，決定開始和結束日期，k 張金牌，若使用則跳過當天，否則拿取當天的收益，求最大收益。
ZeroJudge 連結
解法：動態規劃。
#include <iostream>
using namespace std;
int dp[150001][21];
// dp[i][j] = 第 i 天使用 j 個金牌的最大收益
int main(){
int n, k, x, ans = 0;
cin >> n >> k;
for(int i=1; i<=n; i++){ // 第 i 天
cin >> x;
for(int j=0; j<=k; j++){ // 使用 j 個金牌
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j] + x); // max(使用金牌, 不使用金牌)
ans = max(ans, dp[i][j]);
}
}
cout << ans << '\n';
}