目录
尺取法(双指针法)
二维化一维：
一、
二、
码1：
思路：
码2：
二分+枚举
顾名思义，像尺子一样取一段，满足条件就继续扩大区间，不满足就剔除后端直到满足，然后前端继续前行。
例如二维求子矩阵最大和，可以枚举行长度O(n^2)，然后对于每一列这段和可以理解为1个元素，所有m列就对应了m个元素，也就是化作了怎么用O(n)的时间求最大连续子序列和。
例如二维求最大子矩阵和不超过零的元素个数，同理可以枚举行长度O(n^2)，然后对于每一列这段和可以理解为1个元素，所有m列就对应了m个元素，也就是化作了怎么用O(n)的时间求连续子序列和不超过k的最长长度。
可以枚举行长度O(n^2)，然后对于每一列这段和可以理解为1个元素，所有m列就对应了m个元素，也就是化作了怎么用O(n)的时间求最大连续子序列和(尺取法)。
#include<algorithm> #include<iostream> #include<cstring> #include<string> #include<queue> #include<map> #include<cstdio> #include<cmath> #include<stdlib.h> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int maxn = 1e6+50; int dp[505][505];//dp[i][j]第j列前i项和 int main(){ int n,m; cin >> n >> m; for(int i = 1;i <= n;i++){ for(int j = 1;j <= m;j++){ int x; cin >> x; dp[i][j] = dp[i-1][j]+x; } } int maxs = -5001; for(int i = 1;i <= n;i++){ for(int j = i;j <= n;j++){//双重循环枚举高度及其具体位置 int rec = 0; for(int k = 1;k <= m;k++){//遍历列数 int x = dp[j][k]-dp[i-1][k]; rec += x; maxs = max(maxs,rec);//每一次都要进行判断 if(rec < 0) rec = 0;//如果这个位置<0了，不如置零从头再来(证明这个元素让//rec变小了，肯定不能加进去) } } } cout << maxs << endl; return 0; }可以枚举行长度O(n^2)，然后对于每一列这段和可以理解为1个元素，所有m列就对应了m个元素，也就是化作了怎么用O(n)的时间求连续子序列和不超过k的最长长度(尺取法)。
O(n^3)
#include<iostream> #include<algorithm> #include<cstdio> #include<string> #include<map> #include<cstring> #include<stdlib.h> using namespace std; typedef long long ll; const int maxn = 1e6+50; const int INF = 0x3f3f3f3f; ll _map[300][300]; ll dp[300][300];//dp[i][j] j lie qian i xiang he int main(){ int n,m,l; cin >> n >> m >> l; int f = 0; for(int i = 1;i <= n;i++){ for(int j = 1;j <= m;j++){ cin >> _map[i][j]; if(_map[i][j] > l) f++; dp[i][j] = dp[i-1][j] + _map[i][j]; } } if(f == n*m){ cout << "-1"<<endl; return 0; } int maxs = 0; for(int i = 1;i <= n;i++){ for(int j = i;j <= n;j++){ ll now = 0; int rec = 1; for(int k = 1;k <= m;k++){ now += (dp[j][k]-dp[i-1][k]); if(now <= l) maxs = max(maxs,(k-rec+1)*(j-i+1));//每一次都判断(只要符合条件) if(now > l){ if(k == m) break;//如果不符合了，到末尾了直接break掉， //如果不是末位，去掉最前端继续向前(尺取法)！！记得标记末端位置，rec++； now-=dp[j][rec]-dp[i-1][rec]; rec++; continue; } } } } cout << maxs << endl; return 0; }思路：先枚举高度，在进行二分宽度，在二分while里面进行枚举左上角坐标O(n^3logn)
#include <iostream> #include <cmath> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; ll a[300][300],dp[300][300]; ll n,m,k; ll bestv; void f(ll h){ ll wl=1,wr=m; while(wr>=wl){ ll w=(wl+wr)>>1; if(h*w<=bestv){ wl=w+1; continue; } bool flag2=false; for(ll i=1;i+h-1<=n&&!flag2;i++){ for(ll j=1;j+w-1<=m;j++){ ll x=i+h-1; ll y=j+w-1; if(dp[x][y]-dp[x][j-1]-dp[i-1][y]+dp[i-1][j-1]<=k){ flag2=true; break; } } } if(flag2){ bestv=h*w; wl=w+1; } else wr=w-1; } return ; } int main() { cin>>n>>m>>k; for(ll i=1;i<=n;i++){ for(ll j=1;j<=m;j++){ cin>>a[i][j]; } } dp[0][0]=0; for(ll i=1;i<=n;i++)dp[i][0]=0; for(ll j=1;j<=m;j++)dp[0][j]=0; //预处理前缀和 for(ll i=1;i<=n;i++){ for(ll j=1;j<=m;j++){ dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+a[i][j]; } } bestv=-1; for(ll h=1;h<=n;h++){ f(h); } cout<<bestv<<endl; return 0; }
