A

给出 m 个长度不超过 n 的黑白序列，每次将同色的长度大于 1 的区间换成一个相反颜色的点，求每一列直到到不能操作的最少步数之和。 \(n\le 10^4,m\le100\)。

贪心。

每次操作就是将相邻三个（边界是两个）合并，贪心的想，一定是从中间能消的开始消（尽量每次消除两个区间）。

如果中间两个可行的区间中间的区间个数超过总数一半，那么答案为中间的区间数。

const int N = 1e5 + 9;

int T, n, len, tot, ans;
char s[N];
int a[N];

inline void main() {
    read(n), read(T);
    while (T--) {
        scanf("%s", s+1);
        len = strlen(s+1);
        tot = 0;
        memset(a, 0, sizeof a);
        for (int i = 1; i <= len; ++i) {
            if (s[i] == s[i-1]) a[tot]++;
            else a[++tot] = 1;
        }
        bool flag = false;
        for (int i = 1; i <= tot; ++i) {
            if (a[i] > 1) a[i] = 1, flag = true;
            else a[i] = 0;
        }
        if (!flag) continue;
        int l = tot >> 1, r = l + 1;
        while (l && !a[l]) l--;
        while (r <= tot && !a[r]) r++;
        if (!l) {
            ans += r;
            continue;
        }
        if (r > tot) {
            ans += tot - l + 1;
            continue;
        }
        if ((r - l) * 2 >= tot) ans += r - l + 1;
        else ans += tot / 2 + 1;
    }
    printf("%d\\n", ans);
}

B

题目

n 个商店 m 个物品，每种物品在每个商店有不同的价值，每个商店有交通费，求买完所有物品的最小费用。 \(n\le 100,m\le 16\)。

状压 DP。

设 \(f_{i,S}\) 表示前 i 个商店已购买 S 状态的最小费用。对于每个商店，强制去该商店，更新所有状态，再与不去该商店的状态取 \(\min\)。

const int N = 1e5 + 9;
const int M = 109;

int n, m, maxn;
int f[M][N], val[M][M], fee[M];

inline void main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i) {
        read(fee[i]);
        for (int j = 1; j <= m; ++j)
            read(val[i][j]);
    }
    maxn = (1 << m) - 1;
    memset(f[0], 0x3f, sizeof f[0]);
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= maxn; ++j) {
            f[i][j] = f[i-1][j] + fee[i];
        }
        for (int j = 0; j <= maxn; ++j) {
            for (int k = 1; k <= m; ++k) {
                if ((j & (1 << (k - 1))) == 0) continue;
                f[i][j] = min(f[i][j], f[i][j ^ (1 << (k - 1))] + val[i][k]);
            }
        }
        for (int j = 0; j <= maxn; ++j) {
            f[i][j] = min(f[i][j], f[i-1][j]);
        }
    }
    printf("%d\\n", f[n][maxn]);
}

RenaMoe's Blog

20年11月13日小测

A

B