2013 年騰訊編程馬拉松初賽第 0 場（3 月 20 日），共 5 道題目 HDU 4500~4504，涵蓋模擬、三維背包、01 背包變體、概率組合、博弈 DP。本文逐題給出題意、解法與 AC 代碼。
N×M 矩陣代表工位，每格整數為魅力值（正=女，負=男）。某位置得分 = 四鄰域魅力值絕對值，性別不同則加分，相同則減分。求最高分位置（行優先再列優先）。
直接模擬：遍歷每個格子，檢查上下左右鄰居，按規則累加得分，記錄最大值及座標。N,M ≤ 20，複雜度 O(NM) 極小。
#include <iostream>
#include <cstring>
using namespace std;
int a[25][25], n, m, sum;
void addScore(int x, int y, int val) {
if (x < 1 || x > n || y < 1 || y > m) return;
if (a[x][y] * val < 0) sum += abs(a[x][y]);
else sum -= abs(a[x][y]);
}
int main() {
while (~scanf("%d%d", &n, &m), n||m) {
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d", &a[i][j]);
int maxv = -1e9, ansx, ansy;
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) {
sum = 0;
addScore(i-1,j,a[i][j]); addScore(i+1,j,a[i][j]);
addScore(i,j-1,a[i][j]); addScore(i,j+1,a[i][j]);
if (sum > maxv) { maxv = sum; ansx = i; ansy = j; }
}
printf("%d %d %d\n", ansx, ansy, maxv);
}
return 0;
}
n 件商品，每件有價格 a、積分 b、價值 val。小明有 v1 元現金、v2 積分、可免費拿 k 件。三種支付方式任選其一，每件最多買一次。求最大總價值。n≤100, v1,v2≤100, k≤5。
三維 DP：dp[t][j][k] 表示用 t 次免費機會、j 元現金、k 積分能獲得的最大價值。對每件物品倒序轉移三種選擇。
#include <iostream>
#include <cstring>
using namespace std;
int dp[105][105][105];
struct Item { int a,b,w; } it[105];
int main() {
int n, v1, v2, k;
while (~scanf("%d%d%d%d", &n, &v1, &v2, &k)) {
for (int i=1;i<=n;i++) scanf("%d%d%d", &it[i].a, &it[i].b, &it[i].w);
memset(dp, 0, sizeof(dp));
for (int i=1;i<=n;i++)
for (int t=k;t>=0;t--)
for (int j=v1;j>=0;j--)
for (int kk=v2;kk>=0;kk--) {
int best = dp[t][j][kk];
if (t>0) best = max(best, dp[t-1][j][kk] + it[i].w);
if (j>=it[i].a) best = max(best, dp[t][j-it[i].a][kk] + it[i].w);
if (kk>=it[i].b) best = max(best, dp[t][j][kk-it[i].b] + it[i].w);
dp[t][j][kk] = best;
}
printf("%d\n", dp[k][v1][v2]);
}
return 0;
}
m 天假期，n 份工作，每份有開始 s、結束 e、報酬 c。工作不可重疊（時間段閉區間），求最大報酬。m≤100, n≤1000。
按結束時間排序，dp[i] 表示前 i 天最大報酬。對每份工作，dp[e] = max(dp[e], dp[s-1] + c)，最後輸出 dp[m]。類似區間調度 + 背包。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[105];
struct Job { int s,e,w; } job[1105];
bool cmp(Job a, Job b) { return a.s!=b.s ? a.s m || job[i].s < 1) { i--; n--; }
}
sort(job+1, job+n+1, cmp);
memset(dp, 0, sizeof(dp));
for (int i=1;i<=n;i++)
for (int j=m;j>=job[i].e;j--)
dp[j] = max(dp[j], dp[job[i].s-1] + job[i].w);
printf("%d\n", dp[m]);
}
return 0;
}
n 個孩子，第 i 個有 B_i 個朋友（雙向）。隨機抽 3 人，求他們「全互為朋友」或「全不認識」的概率。n≤1000。
總方案 C(n,3)。不滿足條件的三元組 = 存在恰好一對朋友的三元組。對每條邊 (u,v)，第三人可選其餘 n-2 人中與 u、v 關係不同的人。數學推導得：
bad = Σ B_i * (n-1-B_i) / 2（每條邊被兩端各算一次）。
答案 = 1 - bad / C(n,3)。
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
int T; scanf("%d", &T);
while (T--) {
int n; scanf("%d", &n);
long long sum = 0;
for (int i=1, b;i<=n;i++) { scanf("%d", &b); sum += 1LL*b*(n-1-b); }
sum /= 2;
double total = 1.0 * n * (n-1) * (n-2) / 6;
printf("%.3lf\n", 1.0 - sum / total);
}
return 0;
}
比賽剩 t 秒，雙方輪流進攻，每回合 15 秒（不足 15 秒不得分）。我方先攻，三種進攻得 1/2/3 分，對方固定得 1 分。當前比分 A:B，求我方獲勝的進攻選擇方案數（不考慮命中率）。
計算雙方剩餘回合數：我方 my = (t+14)/15，對方 op = t/15。對方最終分 = B + op。我方需在 my 回合中獲得至少 need = B + op - A + 1 分。每回合得 1/2/3 分，求恰好 my 回合和 ≥ need 的方案數。DP 計數：dp[i][j] 前 i 回合得 j 分方案數。
#include <iostream>
#include <cstring>
using namespace std;
int main() {
int A, B, t;
while (scanf("%d%d%d", &A, &B, &t) == 3) {
int my = (t + 14) / 15, op = t / 15;
int target = B + op - A + 1;
if (target <= 0) { printf("%d\n", (int)pow(3, my)); continue; }
int dp[51][201] = {}; dp[0][0] = 1;
for (int i=1;i<=my;i++)
for (int j=0;j<=3*my;j++)
for (int k=1;k<=3;k++)
if (j>=k) dp[i][j] += dp[i-1][j-k];
int ans = 0;
for (int j=target;j<=3*my;j++) ans += dp[my][j];
printf("%d\n", ans);
}
return 0;
}
