首页 > 代码库 > HDU 5110 Alexandra and COS
HDU 5110 Alexandra and COS
比赛的时候看完就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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。