| 定義式 | 遞推式 | |
| 二維前綴和 |
兩種求二維前綴和的方法：
1、使用兩個陣列
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
int sum[]={0};
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j];2、使用一個陣列（a[i][j]之前的前綴和都已經求出來了，和sum[i][j]等價，實際上就是覆寫一下）
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=a[i][j-1]+a[i-1][j]-a[i-1][j-1]+a[i][j];思路：首先求出二維前綴和，通過二維前綴和的性質可求出指定區域和，
下面是此題AC代碼，
#include<bits/stdc++.h>
using namespace std;
int n,l,r,t,a[601][601],sum[601][601];
int main() {
ios::sync_with_stdio(false);
cin>>n>>l>>r>>t;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
cin>>a[i][j];
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
int res=0;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) {
int max_i=min(n,i+r);
int max_j=min(n,j+r);
int min_i=max(0,i-r-1);
int min_j=max(0,j-r-1);
double tmp=double(sum[max_i][max_j]-sum[min_i][max_j]-sum[max_i][min_j]+sum[min_i][min_j])/double((max_i-min_i)*(max_j-min_j));
if(tmp<=t)
res++;
}
cout<<res;
return 0;
}下面是一維前綴和的介紹和例題解答，
CCF 202012-2 期末預測之最佳閾值 100分（一維前綴和）_m0_47618364的博客-CSDN博客
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/286344.html
標籤：其他