poj3034--Whac-a-Mole（dp）

poj3034--Whac-a-Mole（dp）

題目大意：砸地鼠游戲，n*n的方格，錘子每次最多移動d，地鼠在t時刻出現在(x,y)時間，維持一個單位時間，不會在同一時間同一位置出現兩只老鼠，錘子可以砸經過的地鼠，問最多可以砸多少地鼠。（初始錘子可以在任意位置）

dp[t][i][j]：t時刻在錘子在(i,j)位置時能砸到的最多的地鼠個數

狀態轉移方程：因為錘子最多移動d，所以枚舉（x-d,y-d）到（x+d,y+d）的點（tx,ty），認為這是(x,y)向(tx,ty)移動的第一個點，然後計算在d范圍內的點。統計被砸的地鼠的個數

注意：肯能通過邊界外的點進行移動

20 5 4
1 0 1
0 1 1
0 5 2
1 6 2
0 0 0

所以要將所有的點移動(5,5)的距離，可以避免負坐標

#include 
#include 
#include 
using namespace std ;
int dp[12][41][41] ;
int Map[12][41][41] ;
void f(int n,int t,int x,int y,int d) {
    int i , j , k , p , q , num ;
    for(i = max(0,x-d) ; i <= min(n-1,x+d) ; i++) {
        for(j = max(0,y-d) ; j <= min(n-1,y+d) ; j++) {
            if( i == x && j == y ) continue ;
            p = i - x ;
            q = j - y ;
            k = num = 0 ;
            while( x+k*p >= 0 && x+k*p < n && y+k*q >= 0 && y+k*q < n && k*k*(q*q+p*p) <= d*d ) {
                if( Map[t][x+k*p][y+k*q] ) num++ ;
                dp[t][x][y] = max(dp[t][x][y],dp[t-1][x+k*p][y+k*q]+num) ;
                k++ ;
            }
        }
    }
    return ;
}
int main() {
    int n , d , m ;
    int x , y , t ;
    int i , j , max_t , ans ;
    while( scanf(%d %d %d, &n, &d, &m) && n+d+m != 0 ) {
        memset(dp,0,sizeof(dp)) ;
        memset(Map,0,sizeof(Map)) ;
        max_t = ans = 0 ;
        while( m-- ) {
            scanf(%d %d %d, &x, &y, &t) ;
            Map[t][x+5][y+5] = 1 ;
            max_t = max(max_t,t) ;
        }
        n += 12 ;
        for(t = 1 ; t <= max_t ; t++) {
            for(i = 0 ; i < n ; i++) {
                for(j = 0 ; j < n ; j++) {
                    f(n,t,i,j,d) ;
                    ans = max(ans,dp[t][i][j]) ;
                }
            }
        }
        printf(%d
, ans) ;
    }
    return 0 ;
}