首页 > 代码库 > HDU 5110 Alexandra and COS

HDU 5110 Alexandra and COS

2024-08-03 23:21:10   211人阅读

比赛的时候看完就get到是dp，然后发现要开1000*1000*1000的数组，然后就跪那里起不来了。。。

赛后看题解学会了一种好机智的姿势啊，将第一维降为√1000，对于D小于√m的用dp做，D大于√m的暴力，这样两种做法都是n^2.5，太机智了。

psum是前缀和，xpsum[k][i][j]是D为k时，第i行前j列，i-k行前j+k列，i-2k行前j+2k列...的和，f是答案。

 

#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<cmath>using namespace std;char str[1010];int psum[1010][1010],xpsum[40][1010][1010],f[40][1010][1010];int main(){    int n,m,q;    int x,y,d;    int ans;    while(scanf("%d%d%d",&n,&m,&q)==3) {        for(int i=1;i<=n;++i) {            scanf("%s",str+1);            psum[i][0]=0;            for(int j=1;j<=m;++j) {                psum[i][j]=psum[i][j-1]+(str[j]==‘X‘);            }        }        int B=sqrt(n+0.0);        for(int k=1;k<=B;++k) {            for(int i=1;i<=n;++i) {                for(int j=1;j<=m;++j) {                    f[k][i][j]=0;                    xpsum[k][i][j]=psum[i][j];                    if(i-k>0) {                        if(j+k<=m) xpsum[k][i][j]+=xpsum[k][i-k][j+k];                        else xpsum[k][i][j]+=xpsum[k][i-k][m];                        if(j-k>0) {                            f[k][i][j]=f[k][i-k][j-k];                            f[k][i][j]-=xpsum[k][i-k][j-k];                            if(j+k<=m) f[k][i][j]+=xpsum[k][i-k][j+k];                            else f[k][i][j]+=xpsum[k][i-k][m];                        }                        else {                            if(j+k<=m) f[k][i][j]=xpsum[k][i-k][j+k];                            else f[k][i][j]=xpsum[k][i-k][m];                        }                    }                    f[k][i][j]+=psum[i][j]-psum[i][j-1];                }            }        }        while(q--) {            scanf("%d%d%d",&x,&y,&d);            ans=0;            if(d>B) {                for(int i=x;i>0;i-=d) {                    int l=max(1,y-x+i),r=min(m,y+x-i);                    ans+=psum[i][r]-psum[i][l-1];                }            }            else {                ans=f[d][x][y];            }            printf("%d\n",ans);        }    }}

 

HDU 5110 Alexandra and COS


联系
我们