思路:
用二维前缀统计每个像素对该点的贡献,对二维前缀进行维护,删除重复值
AC代码
#include <iostream> #define ll long long using namespace std; ll a,b,n,m,Max=0; bool img[3845][2165]; int dp[3845][2165]; int main() { cin>>n>>m>>a>>b; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>img[i][j]; } } for(int i=1;i<=a;i++){ for(int j=1;j<=b;j++){//统计像素对该点贡献(n*m以外的则有部分重复) dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+img[i][j]; } } for(int i=a;i>=a-n+2;i--){//删去重复的贡献 for(int j=1;j<=b;j++){ dp[i][j]-=dp[i-a+n-1][j]; } } for(int i=1;i<=a;i++){//删去重复的贡献 for(int j=b;j>=b-m+2;j--){ dp[i][j]-=dp[i][j-b+m-1]; } } for(int i=1;i<=a;i++){ for(int j=1;j<=b;j++){ if(Max<dp[i][j]) Max=dp[i][j]; } } for(int i=1;i<=a;i++){ for(int j=1;j<=b;j++){ cout <<100*dp[i][j]/Max; if(j<b) cout<<" "; else cout<<endl; } } return 0; }