程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj3034

poj3034

編輯:關於C++

 

題目大意:砸地鼠游戲,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
結果是4

 

所以要將所有的點移動(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 ;
}


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved