首页 > ACM题库 > HDU-杭电 > HDU 2881-Jack’s struggle-动态规划-[解题报告]HOJ
2014
02-17

HDU 2881-Jack’s struggle-动态规划-[解题报告]HOJ

Jack’s struggle

问题描述 :

A team of airborne troops are ready to complete some missions.
The battlefield was divided into a grid of n*n, this team can be air-dropped at any place on time 0. In every time unit after landing, they can go to the grid left, right, up or down to the current grid, or they can just stay.
On their mission list, each mission is described as three integers: t, r and c, represents a task that must be completed exactly at time t on the grid (r, c).
Obviously, with limits of time, not all missions can be done.
The captain, Jack, struggling making decisions, wants to know how many missions they can complete at most.

输入:

The input contains serveral cases:

For each case:

* The first line contains two integers n and m, 1<=n<=1000, 1<=m<=10000, n represents the size of the battlefield and m represents the number of missions on the list.

* Following m lines, each one describes a mission using three integers, t, r and c.

No two missions have the same t, r and c.

The input is terminated by n=m=0.

输出:

The input contains serveral cases:

For each case:

* The first line contains two integers n and m, 1<=n<=1000, 1<=m<=10000, n represents the size of the battlefield and m represents the number of missions on the list.

* Following m lines, each one describes a mission using three integers, t, r and c.

No two missions have the same t, r and c.

The input is terminated by n=m=0.

样例输入:

2 2
1 1 1
2 2 2
0 0 

样例输出:

1

点击打开链接

题意:

给你一个n*n的矩阵,矩阵中有m个区域,每个区域都有走过时间的要求,输入m行每行三个数t,x,y,表示走过x,y的时间必须为第t秒,求最多走过少的区域

直接暴力dp就可以了,但是用g++就过了,c++tle,而且之前没用cmath函数,自己写了一个abs函数,但是超时了,该过之后就A了,3000多ms

yf说是天上掉馅饼的二维形式,恩确实如此

#include"stdio.h"
#include"string.h"
#include"algorithm"
#include"cmath"
#define N 10001
using namespace std;

struct node
{
	int t,x,y;
}A[N];

int cmp(node a,node b){return a.t<b.t;}
int max(int a,int b){return a>b?a:b;}

int main()
{
	int n,m;
	int dp[N];
	int i,j,ans;
	while(scanf("%d%d",&n,&m)!=-1&&(n+m))
	{
		for(i=0;i<m;i++)
			scanf("%d%d%d",&A[i].t,&A[i].x,&A[i].y);
		sort(A,A+m,cmp);
		ans=0;
		for(i=0;i<m;i++)
		{
			dp[i]=1;
			for(j=0;j<i;j++)
			{
				if(abs(A[i].t-A[j].t)>=(abs(A[i].x-A[j].x)+abs(A[i].y-A[j].y)))
					dp[i]=max(dp[i],dp[j]+1);
			}
			if(dp[i]>ans)ans=dp[i];
		}
		printf("%d\n",ans);
	}
	return 0;
}

解题参考:http://blog.csdn.net/yangyafeiac/article/details/9621327


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。