您好,登錄后才能下訂單哦!
這篇文章將為大家詳細(xì)講解有關(guān)ACwing中的二維前綴和怎么用,文章內(nèi)容質(zhì)量較高,因此小編分享給大家做個(gè)參考,希望大家閱讀完這篇文章后對(duì)相關(guān)知識(shí)有一定的了解。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N=5010; int n,m; int s[N][N]; int main(){ int cnt,R; cin>>cnt>>R; //優(yōu)化 R=min(5001,R); //防止右下角空 n=m=R; while(cnt--){ int x,y,w; cin>>x>>y>>w; x++,y++; n=max(n,x); m=max(m,y); s[x][y]+=w; } //預(yù)處理前綴和 for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1]; } } int wmax=0; //枚舉所有變長(zhǎng)為R的矩形,枚舉矩形右下角坐標(biāo)(i,j) for(int i=R;i<=n;i++){ for(int j=R;j<=m;j++){ wmax=max(wmax,s[i][j]-s[i-R][j]-s[i][j-R]+s[i-R][j-R]); } } cout<<wmax; return 0; }
關(guān)于ACwing中的二維前綴和怎么用就分享到這里了,希望以上內(nèi)容可以對(duì)大家有一定的幫助,可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò),可以把它分享出去讓更多的人看到。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。