2020牛客暑期多校第二场 F - Fake Maxpooling（dp/单调队列）[待补]_综合

传送门

方法一：dp

这个做法还是很神奇的。当 $k>1$ 时，考虑一个 $k*k$ 的子矩阵，我们将最大值假定为右下角的值，那么我们统计答案时，只需要统计矩阵 $[(k,k),(n,m)]$ ，而 $k*k$ 的子矩阵一定可以由若干个重叠的 $2*2$ 的矩阵构成，那么我们就只需要每次将左边和上面的最值传递到当前位置，这样最后的答案和最后的矩阵没有关系，只和统计开始的行列有关系

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;int gcd[5005][5005],lcm[5005][5005];inline int max(int x,int y){return x>y?x:y;
}int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n,m,K;scanf("%d%d%d",&n,&m,&K);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) if(!gcd[i][j])for(int k=1;i*k<=n && j*k<=m;k++)gcd[i*k][j*k]=k,lcm[i*k][j*k]=i*j*k;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(K!=1) lcm[i][j]=max(lcm[i][j],max(lcm[i-1][j],lcm[i][j-1]));ll ans=0;for(int i=K;i<=n;i++)for(int j=K;j<=m;j++)ans+=lcm[i][j];printf("%lld\n",ans);return 0;
}

方法二：单调队列

留坑