题意：给你一个n*m的矩阵 ，每个位置都有一个字符并且都有一个值，现在需要找到一个p*q的子矩阵， 原来的矩阵可以由现在这个矩阵无限复制然后截取其中的一部分得到，并且要求 子矩阵里最大的值 * (p+1)*(q+1)的值最小。
题解：对于每一行处理出可能的循环节长度， 然后找到一个长度是所有行的循环节， 对于列同样处理。然后问题就变成了对n*m所有的p*q的子矩阵的找到最小的最大值。这个操作用单调队列维护。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); 4 #define LL long long 5 #define ULL unsigned LL 6 #define fi first 7 #define se second 8 #define pb push_back 9 #define lson l,m,rt<<1 10 #define rson m+1,r,rt<<1|1 11 #define max3(a,b,c) max(a,max(b,c)) 12 #define min3(a,b,c) min(a,min(b,c)) 13 typedef pair<int,int> pll; 14 const int inf = 0x3f3f3f3f; 15 const LL INF = 0x3f3f3f3f3f3f3f3f; 16 const LL mod = (int)1e9+7; 17 const int N = 1e6 + 100; 18 string s, ss; 19 int val[N]; 20 int nx[N]; 21 int n, m; 22 inline int id(int x, int y){ 23 return m * x + y; 24 } 25 int cnt[N]; 26 void get_nt(int u){ 27 nx[0] = -1; 28 int j = 0, k = -1; 29 while(j < m){ 30 if(k == -1 || s[id(u,j)] == s[id(u,k)]) nx[++j] = ++k; 31 else k = nx[k]; 32 } 33 int pos = m; 34 while(pos != -1){ 35 cnt[m-pos]++; 36 pos = nx[pos]; 37 } 38 } 39 void get_nt_(int u){ 40 nx[0] = -1; 41 int j = 0, k = -1; 42 while(j < n){ 43 if(k == -1 || s[id(j,u)] == s[id(k,u)]) nx[++j] = ++k; 44 else k = nx[k]; 45 } 46 int pos = n; 47 while(pos != -1){ 48 cnt[n-pos]++; 49 pos = nx[pos]; 50 } 51 } 52 int a[N]; 53 LL mx[N]; 54 int main(){ 55 scanf("%d%d", &n, &m); 56 for(int i = 1; i <= n; i++){ 57 cin >> ss; 58 s += ss; 59 } 60 for(int i = 0; i < n*m; i++) 61 scanf("%d", &val[i]); 62 int p = 1, q = 1; 63 memset(cnt, 0, sizeof(cnt)); 64 for(int i = 0; i < n; i++) get_nt(i); 65 for(int i = 1; i <= m; i++){ 66 if(cnt[i] == n) { 67 p = i; 68 break; 69 } 70 } 71 memset(cnt, 0, sizeof(cnt)); 72 for(int i = 0; i < m; i++) get_nt_(i); 73 for(int i = 1; i <= n; i++){ 74 if(cnt[i] == m) { 75 q = i; 76 break; 77 } 78 } 79 /// q*p 80 for(int i = 0; i < n; i++){ 81 int l = 0 , r = -1; 82 for(int j = 0; j < m; j++){ 83 while(r >= l && val[id(i,a[r])] <= val[id(i,j)]) r--; 84 a[++r] = j; 85 while(r >= l && a[l] <= j-p) l++; 86 mx[id(i,j)] = val[id(i,a[l])]; 87 } 88 } 89 LL ans = INF; 90 for(int j = p-1; j < m; j++){ 91 int l = 0 , r = -1; 92 for(int i = 0; i < n; i++){ 93 while(r >= l && mx[id(a[r],j)] <= mx[id(i,j)]) r--; 94 a[++r] = i; 95 while(r >= l && a[l] <= i-q) l++; 96 if(i >= q-1) ans = min(ans, mx[id(a[l],j)]); 97 } 98 } 99 printf("%lld\n",1ll*ans*(p+1)*(q+1)); 100 return 0; 101 }
View Code
转载于:https://www.cnblogs.com/MingSD/p/9360604.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/101527.html原文链接：https://javaforall.net
