hdu5110 dp

题意 给 了 一 个 矩 阵 然 后 ， 潜 艇 可 以 向 前 在 西北和东北之间 的区域， 然后每个潜艇有一个值D ，当到达潜艇距离为D的倍数的时候可以得到这个价值，这样我们1000*1000 的矩阵，D<=1000, dp这么多显然是不可以的，那么对于大于sqrt(n); 直接暴力， 对于小于sqrt(n) 的进行dp 

dp[i][j][k]=dp[i-k][j-k][k]+dp[i-k][j+k][k]-dp[i-k-k][j][k]+num[i-k][j+k-1]-num[i-k][j-k]

j-k

不存在时 dp[i][j][k]=dp[i-k][j+k][k]+num[i-k][j+k-1]-num[i-k][0]+num[i-k-k][j+k-1]-num[i-k-k][0];

j+k

不存在时 dp[i][j][k]=dp[i-k][j-k][k]+num[i-k][M]-num[i-k][j-k]+num[i-k-k][M]-num[i-k-k][j];

两个都不存在时，我们就定义dp[i][j][k]=dp[i-k][M][k]+num[i-k][M-1]+num[i-k][0]+num[i-k-k][M-K-1]-num[i-k-k][0]

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string.h>
#include <cmath>
using namespace std;
const int maxn= 1005;
int N,M,Q;
int dp[maxn][maxn][32];
char str[maxn][maxn];
int num[maxn][maxn];
int X[maxn*500],Y[maxn*500],D[maxn*500];
int solve(int x, int y, int d){if(d==0){return num[x][y]-num[x][y-1];}int L=y,R=y;int  ans=0;while(x>0){ans+= num[x][R]-num[x][L-1];x -= d;L=max( 1 , L - d );R=min( R + d ,M  );}return ans;
}
int main()
{while(scanf("%d%d%d",&N,&M,&Q)==3){for(int i=1; i<=N; ++i){scanf("%s",str[i]+1);num[i][0]=0;for(int j=1; j<=M; ++j)if(str[i][j]=='X')num[i][j]=num[i][j-1]+1;else num[i][j]=num[i][j-1];}int maxD=0;for(int i=0; i<Q; ++i ){scanf("%d%d%d",&X[i],&Y[i],&D[i]);maxD=max(maxD,D[i]);}maxD=min(double (maxD) ,sqrt(N+0.5) );for(int i=1; i<=N; ++i)for(int j=1; j<=M; ++j)for(int k =1 ; k <= maxD; ++k){dp[i][j][k]=str[i][j]=='X'?1:0;if(i-k>0){if(j-k>0&&j+k<=M){dp[i][j][k]+=dp[i-k][j-k][k]+dp[i-k][j+k][k];dp[i][j][k]+=num[i-k][j+k-1]-num[i-k][j-k];if(i-2*k>0)dp[i][j][k]-=dp[i-2*k][j][k];}else if(j-k>0){dp[i][j][k]+=dp[i-k][j-k][k]+num[i-k][M]-num[i-k][j-k];if(i-k-k>0)dp[i][j][k]+=num[i-k-k][M]-num[i-k-k][j];}else if(j+k<=M){dp[i][j][k]+=dp[i-k][j+k][k]+num[i-k][j+k-1]-num[i-k][0];if(i-k-k>0)dp[i][j][k]+=num[i-k-k][j-1]-num[i-k-k][0];}else{dp[i][j][k]+=dp[i-k][M][k]+num[i-k][M-1]-num[i-k][0];if(M-k>0&&i-k-k>0)dp[i][j][k]+=num[i-k-k][M-k-1]-num[i-k-k][0];}}}for(int i=0; i<Q; ++i){if(D[i]<=maxD)printf("%d\n",dp[X[i]][Y[i]][D[i]]);else printf("%d\n",solve(X[i],Y[i],D[i]));}}return 0;
}