E-carpet
白云 “的长方形地毯是$n*m$ $Grid (i,j)$的颜色为$colorA[i][j]$,成本为$costA[i][j]$。
小白兔将从$A$中选择一个$p*q$的子矩形$B$,每个网格的颜色为$colorB[0…p-1][0…q-1]$,$B$的成本为(相应子矩形$costA*(p+1)*(q+1)$中的最大数字)。
然后将$colorB$连续平移并复制无限次,即将$colorB$扩展为满足$colorC[i][j]=colorB[i mod p][j mod q]$的无限个新矩阵$colorC$。
小白兔必须确保 $colorA$是 $colorC$的子矩形。
您需要找到成本最小的方法。
think
二维hash kmp + 二维 滑窗
code
// NowCoder carpet
// https://ac.nowcoder.com/acm/contest/27589/E 2024-04-05 15:08:33
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
void solve() {
cin >> n >> m;
vector<vector<char>> a(n + 2, vector<char>(m + 2));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
vector<int> hash1(n + 2);
vector<int> hash2(m + 2);
const int mod = 1E9 + 7, base = 131;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
hash1[i] = (hash1[i] * base + a[i][j] - 'a' + 1) % mod;
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
hash2[i] = (hash2[i] * base + a[j][i] - 'a' + 1) % mod;
}
}
// for (int i = 1; i <= n; i++) {
// cout << hash1[i] << " ";
// }
// cout << "\n";
// for (int i = 1; i <= m; i++) {
// cout << hash2[i] << " ";
// }
// cout << "\n";
vector<int> nxt1(n + 1);
vector<int> nxt2(m + 1);
for (int i = 2, j = 0; i <= n; i++) {
while (j and hash1[j + 1] != hash1[i]) j = nxt1[j];
if (hash1[j + 1] == hash1[i]) j++;
nxt1[i] = j;
}
// for (int i = 1; i <= n; i++) cout << nxt1[i] << " ";
// cout << "\n";
for (int i = 2, j = 0; i <= m; i++) {
while (j and hash2[j + 1] != hash2[i]) j = nxt2[j];
if (hash2[j + 1] == hash2[i]) j++;
nxt2[i] = j;
}
// for (int i = 1; i <= m; i++) cout << nxt2[i] << " ";
// cout << "\n";
int s = n - nxt1[n];
int t = m - nxt2[m];
// cout << s << " " << t << "\n";
vector<vector<int>> cost(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) cin >> cost[i][j];
deque<int> q;
int ans = INT_MAX;
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++) {
// cout << cost[i][j] << " ";
// }
// cout << "\n";
// }
for (int i = 1; i <= n; i++) {
while (q.size()) q.pop_back();
for (int j = 1; j <= m; j++) {
while (q.size() and cost[i][q.back()] <= cost[i][j]) q.pop_back();
q.push_back(j);
while (q.size() and q.front() <= j - t) q.pop_front();
if (j - t + 1 >= 1) cost[i][j - t + 1] = min(ans, cost[i][q.front()]);
}
}
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++) {
// cout << cost[i][j] << " ";
// }
// cout << "\n";
// }
for (int j = 1; j <= m - t + 1; j++) {
while (q.size()) q.pop_back();
for (int i = 1; i <= n; i++) {
while (q.size() and cost[q.back()][j] <= cost[i][j]) q.pop_back();
q.push_back(i);
while (q.size() and q.front() <= i - s) q.pop_front();
if (i - s + 1 >= 1) cost[i - s + 1][j] = min(ans, cost[q.front()][j]);
}
}
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++) {
// cout << cost[i][j] << " ";
// }
// cout << "\n";
// }
// cout << ans << "\n";
for (int i = 1; i <= n - s + 1; i++) {
for (int j = 1; j <= m - t + 1; j++) {
ans = min(ans, cost[i][j]);
}
}
cout << ans * (t + 1) * (s + 1) << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}