POJ3034WhacaMoleDP

题意&＃xff1a;在一个n*n的矩阵中&＃xff0c;每个&＃xff08;x,y&＃xff09;坐标有个洞&＃xff0c;在任意时刻&＃xff08;从上一时刻开始到目前时刻结束&＃xff09;&＃xff0c;任意位置可能会探出一个鼹鼠的头&＃xff0c;如果用锤子 打中即得一分&＃xff0c;锤子活动的范围是以d(1&＃61;
题解&＃xff1a;动态规划&＃xff0c;最优结果由子问题的最优结果得出。注意的是&＃xff1a;锤子可以移动到矩阵之外。
在一个确定的时刻&＃xff0c;每个点作为endpoints可得多少分,在下一时刻&＃xff0c;每个点作为endpoints可得多少分为&＃xff1a;         
 dp[i][j][k]&＃61;max{dp[x~][y~][k-1]&＃43;Mole[x][y][k]}
表示以(x~,y~)为起始坐标&＃xff0c;i,j为目标坐标&＃xff0c;在上一时刻(x~,y~)得到的最多分加上沿路可得到的分&＃xff1b;
取这些可选路线中使第k时刻以(i,j)为目标坐标得到最多分的路线放在dp[i][j][k].
以上转自&＃xff1a;
http://wangjia007bond.blog.163.com/blog/static/304220242009102695054442/

注意&＃xff1a;锤子没有要求一定要落在n*n游戏盘面中&＃xff0c;有可能某一时刻落在盘外&＃xff0c;在下一时刻&＃xff0c;由盘外沿直线进入盘内。


#include
#include
using namespace std;#define max(a,b) ( a > b ? a : b )bool map[32][32][11];
int dp[32][32][11];
int n, d, m;int gcd ( int a, int b )
{return (a &＃61;&＃61; 0) ? b : gcd ( b % a, a );
}int get_sum ( int x1, int y1, int x2, int y2, int t )
{int i, dx, dy, g, sum &＃61; 0; dx &＃61; x2 - x1;dy &＃61; y2 - y1;if ( dx * dx &＃43; dy * dy > d * d ) return 0;if ( dx &＃61;&＃61; 0 && dy &＃61;&＃61; 0 )return map[x2][y2][t];if ( dx &＃61;&＃61; 0 ){if ( y1 > y2 ) swap(y1, y2);for ( i &＃61; y1; i <&＃61; y2; i&＃43;&＃43; )sum &＃43;&＃61; map[x2][i][t];return sum;}if ( dy &＃61;&＃61; 0 ){if ( x1 > x2 ) swap(x1, x2);for ( i &＃61; x1; i <&＃61; x2; i&＃43;&＃43; )sum &＃43;&＃61; map[i][y1][t];return sum;}g &＃61; gcd ( abs(dx), abs(dy) );dx &＃61; dx / g; dy &＃61; dy / g;for ( i &＃61; 0; i <&＃61; g; i&＃43;&＃43; )sum &＃43;&＃61; map[x1&＃43;i*dx][y1&＃43;i*dy][t];return sum;
}int main()
{int i, j, x, y, t, mt;int sx, tx, sy, ty, ans;while ( scanf("%d%d%d",&n,&d,&m) ){if ( n &＃43; d &＃43; m &＃61;&＃61; 0 ) break;memset(map,0,sizeof(map));memset(dp,0,sizeof(dp));ans &＃61; mt &＃61; 0;for ( i &＃61; 1; i <&＃61; m; i&＃43;&＃43; ){scanf("%d%d%d",&x,&y,&t);map[x&＃43;d][y&＃43;d][t] &＃61; 1;if ( t > mt ) mt &＃61; t;}n &＃61; n &＃43; 2 * d;for ( t &＃61; 1; t <&＃61; mt; t&＃43;&＃43; ){for ( x &＃61; 0; x &＃61; n ? n - 1 : x &＃43; d;sy &＃61; y - d <0 ? 0 : y - d;ty &＃61; y &＃43; d >&＃61; n ? n - 1 : y &＃43; d;for ( i &＃61; sx; i <&＃61; tx; i&＃43;&＃43; ){for ( j &＃61; sy; j <&＃61; ty; j&＃43;&＃43; ){if ( (i-x)*(i-x) &＃43; (j-y)*(j-y) <&＃61; d*d )dp[x][y][t] &＃61; max ( dp[x][y][t], get_sum ( i, j, x, y, t ) &＃43; dp[i][j][t-1] );}}if ( t &＃61;&＃61; mt && dp[x][y][t] > ans ) ans &＃61; dp[x][y][t];}}}printf("%d\n",ans);}return 0;
}