T1
Topcoder SRM 593 div2 Hard - MayTheBestPetWin
由于每个宠物都要被分到一组中，所以只需要知道一组中的 \(\sum mx - \sum mn\) 就可以推出另一组的 \(\sum mx - \sum mn\)。然后直接背包 dp 即可。
代码
#include <iostream>
using namespace std;
const int N = 500000;
int dp[51][1000005];
int n;
int mx[55], mn[55], Mx, Mn;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> mn[i], Mn += mn[i];
cin >> n;
for (int i = 1; i <= n; i++) cin >> mx[i], Mx += mx[i];
dp[0][N] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= N + N; j++) {
if (j >= mx[i])
dp[i][j] |= dp[i - 1][j - mx[i]];
if (j + mn[i] <= N + N)
dp[i][j] |= dp[i - 1][j + mn[i]];
}
}
int ans = 2147483647;
for (int i = 0; i <= N + N; i++) {
if (dp[n][i]) {
int x = i - N;
ans = min(ans, max(abs(x), abs(-(x - Mx + Mn))));
}
}
cout << ans << "\n";
return 0;
}
T2
Topcoder SRM 600 div1 Medium - PalindromeMatrix
先二进制枚举出强制哪些列回文，然后考虑行。把上下两个对称的行一块考虑，令 \(cst_{i, 0/1/2}\) 表示第 \(i\) 行和第 \(n - i + 1\) 行中保证所有枚举到的列在这两行上的数相等且这两行中有 \(0 / 1 / 2\) 行回文的最小代价。然后就可以背包 dp 求出有至少 \(rc\) 行回文的最小代价。算 \(cst\) 就枚举列然后分讨。
代码
#include <iostream>
#include <string.h>
using namespace std;
int n, m, cc, cr;
string str[15];
int dp[15][15];
int calc(int S) {
memset(dp, 63, sizeof dp);
dp[0][0] = 0;
int ret = 2147483647;
for (int i = 1; i <= n / 2; i++) {
int x = i, y = n + 1 - i;
int zero = 0, one = 0, two = 0;
for (int j = 1; j <= m / 2; j++) {
int a = j, b = m + 1 - j;
int i1 = ((S >> (a - 1)) & 1), i2 = ((S >> (b - 1)) & 1);
zero += (i1 && (str[x][a] != str[y][a])) + (i2 && (str[x][b] != str[y][b]));
if (!(i1) && !(i2))
two += ((str[x][a] != str[x][b]) + (str[y][a] != str[y][b]));
else
two += min(str[x][a] + str[x][b] + str[y][a] + str[y][b], 4 - (str[x][a] + str[x][b] + str[y][a] + str[y][b]));
}
int t1 = 0, t2 = 0;
for (int j = 1; j <= m / 2; j++) {
int a = j, b = m + 1 - j;
int i1 = ((S >> (a - 1)) & 1), i2 = ((S >> (b - 1)) & 1);
if (i1 && i2) {
t1 += min(str[x][a] + str[x][b] + str[y][a] + str[y][b], 4 - (str[x][a] + str[x][b] + str[y][a] + str[y][b]));
t2 += min(str[x][a] + str[x][b] + str[y][a] + str[y][b], 4 - (str[x][a] + str[x][b] + str[y][a] + str[y][b]));
} else if ((!i1) && (!i2)) {
t1 += str[x][a] != str[x][b];
t2 += str[y][a] != str[y][b];
} else if (i1) {
t1 += min(str[x][a] + str[x][b] + str[y][a], 3 - (str[x][a] + str[x][b] + str[y][a]));
t2 += min(str[x][a] + str[y][a] + str[y][b], 3 - (str[x][a] + str[y][a] + str[y][b]));
} else {
t1 += min(str[x][a] + str[x][b] + str[y][b], 3 - (str[x][a] + str[x][b] + str[y][b]));
t2 += min(str[x][b] + str[y][a] + str[y][b], 3 - (str[x][b] + str[y][a] + str[y][b]));
}
}
one = min(t1, t2);
for (int j = 0; j <= i * 2; j++) {
dp[i][j] = min(dp[i][j], dp[i - 1][j] + zero);
if (j >= 1)
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + one);
if (j >= 2)
dp[i][j] = min(dp[i][j], dp[i - 1][j - 2] + two);
}
}
for (int i = cr; i <= n; i++) ret = min(ret, dp[n / 2][i]);
return ret;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> str[i], str[i] = ' ' + str[i];
m = (int)str[1].size() - 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
str[i][j] -= '0';
}
cin >> cr >> cc;
int ans = 2147483647;
for (int i = 0; i < (1 << m); i++) {
if (__builtin_popcount(i) >= cc)
ans = min(ans, calc(i));
}
cout << ans << "\n";
return 0;
}
T3
Topcoder SRM 584 div1 Medium - Excavations
考虑一个 \(k\) 元组合法的条件，设 \(mindep_x\) 表示所有选出的第 \(x\) 种建筑中最小的深度，也就是 \(\max\limits_{u \in found} mindep_u < \min\limits _{v \notin found}mindep_v\)。所以可以枚举
标签：min,int,t1,20240409,str,mx,dp From： https://www.cnblogs.com/forgotmyhandle/p/18129256