给出一个字符矩阵, 现在把每一列变成相同的字符, 问使得连续列都是相同字符的长度>=x且<=y的最小花费是多少.
考虑这个字符矩阵的行是没有真实作用的. 其实就是将这个字符矩阵换为两个长度为列数的数组, 此后就是简单的dp了.
新字符如果和前面相同, 转移;
新字符和前面不同, 只有当前面的字符连续个数达到x个(当然也要小于y)才能转移.
新知识: 如果实在不知道初态怎么设, 可以先将第一个(dp[1])手动算出, 然后循环中从2开始就好了.
#include<bits/stdc++.h> #define enter puts("") using namespace std; typedef long long ll; inline ll read() { ll x = 0; int f = 0; char ch = getchar(); while (ch < '0' || ch > '9') f |= (ch == '-'), ch = getchar(); while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); return x = f ? -x : x; } inline void write(ll x) { if (x == 0) { putchar('0'); return; } if (x < 0) { putchar('-'); x = -x; } static char s[23]; int l = 0; while (x != 0)s[l++] = x % 10 + 48, x /= 10; while (l)putchar(s[--l]); } template<class T, class U> inline void checkMin(T &x, U y) { if (y < x) x = y; } const int inf = 0x3f3f3f3f; // HAVE FREE OPEN IN MAIN FUNCTION int n, m, x, y; int dp[1005][1005][2]; // i j k // k表示.还是# // 到第i位k类延续了j列. char a[1005][1005]; int p[1005]; int q[1005]; void init() { n = read(), m = read(), x = read(), y = read(); for (int i = 0; i < n; i++) { scanf("%s", a[i]); } for (int j = 0; j < m; ++j) { int cnt = 0; for (int i = 0; i < n; ++i) { if (a[i][j] == '.')cnt++; } p[j + 1] = cnt; q[j + 1] = n - cnt; } // for (int l = 1; l <= m; ++l) { // printf("%d %d\n", p[l], q[l]); // } fill(dp[0][0], dp[0][0] + 1005 * 1005 * 2, inf); dp[1][1][1] = q[1]; dp[1][1][0] = p[1]; for (int i = 2; i <= m; ++i) { for (int j = 1; j <= min(y, i); ++j) { checkMin(dp[i][j][1], dp[i - 1][j - 1][1] + q[i]); if (j >= x)checkMin(dp[i][1][1], dp[i - 1][j][0] + q[i]); checkMin(dp[i][j][0], dp[i - 1][j - 1][0] + p[i]); if (j >= x)checkMin(dp[i][1][0], dp[i - 1][j][1] + p[i]); } } int ans = inf; for (int k = x; k <= y; ++k) { checkMin(ans, dp[m][k][0]); } for (int k = x; k <= y; ++k) { checkMin(ans, dp[m][k][1]); } write(ans); enter; } void solve() { } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif init(); solve(); return 0; }
