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
",dp[X[i]][Y[i]][D[i]]);
             else printf("%d
",solve(X[i],Y[i],D[i]));
        }

    }
    return 0;
}

View Code