Jedi Knights are often tasked with protection. Whether protecting shield generators or important
diplomats, the Jedi will use their lightsabers to deflect blaster shots and keep their asset safe.
Sometimes a Jedi will go on missions alone or will be accompanied by another Jedi. When
protecting an asset, they will stand side by side deflecting shots that would otherwise harm the
asset they wish to protect. Sometimes, even together, they cannot block all the blaster shots.
That is because Jedi are still limited by their physical reaction time. More specifically, when a
Jedi blocks a blaster shot, he has to wait a certain amount of time before he can block another
shot. For example, a Jedi that takes t time units between shots can block a shot arriving at time k
and a shot arriving at time k + t (or later).
So, Jedi will coordinate which shots they each will block and which shots they will allow to pass
through their defense. Either Jedi can independently block each shot as long as there is enough
time between the current shot and his last blocked shot. But determining which shots to block
and which to let by is no easy task if they want to minimize the number of shots that reach their
asset. That is why they seek aid from the other great power in the galaxy, programming.
As the Jedi’s knowledge of programming is not as deep as their knowledge of the force, they
have asked the programmers of the Universal Computational Federation (UCF) to find better
strategies for blocking blaster shots with their lightsabers.
The Problem:
Given the times the blasters reach the Jedi, the number of Jedi, and their reaction time, determine
the number of blaster shots that reach the asset they are trying to protect. Note that each Jedi can
block a blaster shot at the beginning of the mission but after his first block the Jedi is limited by
his reflexes (the time he has to wait before he can block another shot).
The Input:
The first input line contains a positive integer, n, indicating the number of protection missions
the Jedi have been assigned. This is followed by the data for each mission. The first input line
for each mission contains an integer, b (1 ≤ b ≤ 1,000), the number of blaster shots fired at their
asset. This is followed by a line containing b numbers, separated by spaces, which are the times
the blaster shots will reach the Jedi. These numbers can be in any order but will be positive
integers less than 1,000,000. This is followed by an integer j (1 ≤ j ≤ 2) on a line by itself, which
is the number of Jedi on the mission. The last input line for a mission contains j space separated
integers giving the reaction time of each Jedi, the time it takes a Jedi to prepare to block the next
blaster shot. These numbers will be between 1 and 100 inclusive.
The Output:
For each mission, output “Mission #m: a” where m is the mission number (starting with 1)
and a is the minimum number of blaster shots that the Jedi are unable to block and will hit their
asset. Leave a blank line after the output for each mission.
Sample Input:
4
5
10 5 5 10 5
1
100
4
2 4 9 9
2
10 7
5
2 4 8 13 13
2
10 7
5
2 4 6 8 10
1
2
Sample Output:
Mission #1: 4
Mission #2: 1
Mission #3: 1
Mission #4: 0
Explanation of the Sample Input/Output:
In Mission #2, Jedi with speed 7 can block 2 and one 9 and Jedi with speed 10 can block 4,
resulting in one shot remaining unblocked.
In Mission #3, Jedi with speed 7 can block 4 and one 13 and Jedi with speed 10 can block 2 and
the other 13, resulting in one shot remaining unblocked.
大意就是给你若干个时间点作为有射击，会有一个或两个人帮你挡子弹，但是他们的防护有反应时间，求你受到的最少的攻击次数
思路：一个人直接遍历；两个人的时候通过dfs加上数组记录求过的情况（剪枝）来缩短运算时间即可。
题目
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<stack>
#include<set>
using namespace std;
typedef long long ll;
const int N=1000010;
const int inf=0x3f3f3f;
int n,k,m,coun;
int f1,f2;
int f[1000][50][50];
int mk[1010];
void check()
{
int x=mk[0];
for(int i=1;i<m;++i)
{
if(mk[i]-x>=f1)
x=mk[i];
else
coun++;
}
}
int dfs(int x,int u,int fr)
{
if(fr>=m)
return 0;
int d;
if(fr==0)
d=mk[0];
else
d=mk[fr]-mk[fr-1];
x=max(x-d,0);
u=max(u-d,0); //将坐标转换成距离当前点的距离，若可以取（小于等于0）则取0。
if(f[fr][x][u]<inf)
return f[fr][x][u];
if(!u&&!x)
{
f[fr][x][u]=min(dfs(f1,u,fr+1),dfs(x,f2,fr+1));
return f[fr][x][u];
}
else if(!x)
{
f[fr][x][u]=dfs(f1,u,fr+1);
return f[fr][x][u];
}
else if(!u)
{
f[fr][x][u]=dfs(x,f2,fr+1);
return f[fr][x][u];
}
else
{
f[fr][x][u]=dfs(x,u,fr+1)+1;
return f[fr][x][u];
}
}
int main() {
cin>>n;
for(int i=1;i<=n;i++)
{
int t;
coun=0;
memset(f,0x3f,sizeof(f));
printf("Mission #%d: ",i);
cin>>m;
for(int j=0;j<m;j++)
{
scanf("%d",&mk[j]);
}
sort(mk,mk+m);
scanf("%d%d",&t,&f1);
if(t==1)
{
check();
printf("%d\n\n",coun);
}
else
{
scanf("%d",&f2);
printf("%d\n\n",dfs(0,0,0));
}
}
return 0;
}
