首页 > ACM题库 > HDU-杭电 > HDU 3646-Fate Stay Night[解题报告]HOJ
2014
11-30

HDU 3646-Fate Stay Night[解题报告]HOJ

Fate Stay Night

问题描述 :

Jack was addicted to a fighting game recently. The game is similar to a famous anime “Fate Stay Night”. In the game, you should control your “servant” Saber to fight another “servant” Berserker.

Berserker is a famous hero who has a lot of lives. In every life, he has some “blood points”. For example, he may have 100 blood points in his first life and 200 blood points in his second life. When Berserker loss all blood points in a life, he is killed. But he will become alive immediately with next life. When there is no next life left, Berserker is really dead and you win.
Saber can attack Berserker for N times. During each attack, Saber releases a fire bird to fight Berserker. Each fire bird has some “power points”.
A fire bird can make Berserker loss blood points. But if Berserker loss one blood point, the fire bird also will loss one power point. When the power points of a fire bird become zero, the fire bird dies.
A living fire bird may be in two statuses:“young”or “old”.
When a fire bird is just released, it is “young”. After it kills Berserker once or more, it becomes“old”.
Let’s suppose a fire bird with remaining n power points fighting Berserker with remaining m blood points in his current life:
If n> m: Berserker will be killed and becomes alive immediately with his next life(if he has), and then the fire bird will be“old”and fight Berserker again with remaining n-m power points.

If n = m: Berserker will be killed and becomes alive with his next life (if he has), and the fire bird dies.

If n < m: In this situation, if the fire bird is “young”, it will die after making Berserker loss n blood points. But if the fire bird is “old”, it just dies without doing any harm to Berserker.

As the “Master” of Saber, you can use “Command Mantra” M times. You can use “Command Mantra”to double a fire bird’s power points, but you can’t use “Command Mantra”more than once on a same fire bird. Now there is the question: How many times can you kill Berserker at most?

输入:

There are several data cases, ended with “0 0 0”
For each test case:
The first line contains three integers N,M,K, meaning the number of attacks of Saber, the times of Command Mantra you can use and the number of lives of Berserker.
The second line contains N integers, indicating the power points of N fire birds, in the order of attacking. You can’t change the attacking order.

The third line contains K integers, meaning the blood points of all Berserker’s lives. The first integer is for his first life, the second integer is for his second life, etc.
Please note: 1<=N<=10000, 0<=M<=100, 0<=K<=100000. All power points and blood points are no more than 10000 and none negative.

输出:

There are several data cases, ended with “0 0 0”
For each test case:
The first line contains three integers N,M,K, meaning the number of attacks of Saber, the times of Command Mantra you can use and the number of lives of Berserker.
The second line contains N integers, indicating the power points of N fire birds, in the order of attacking. You can’t change the attacking order.

The third line contains K integers, meaning the blood points of all Berserker’s lives. The first integer is for his first life, the second integer is for his second life, etc.
Please note: 1<=N<=10000, 0<=M<=100, 0<=K<=100000. All power points and blood points are no more than 10000 and none negative.

样例输入:

10 0 20
8 9 8 7 5 7 5 5 0 2 
3 0 2 1 7 1 5 5 7 0 6 1 5 6 7 3 1 0 5 8 
10 1 0
6 0 0 7 7 7 1 7 6 7
0 0 0

样例输出:

12
0

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MN 110000

int A[MN],B[MN],C[MN];
int F[11000][101],G[11000][101];
int N,M,K,ans,k;

void upd( int a, int b, int c, int d)
{
	ans=max(ans,c-1);
	if (F[a][b]<c||(F[a][b]==c&&G[a][b]<d))
		F[a][b]=c,G[a][b]=d;
}

int Calc( int k, int s, int m)
{
	C[k]-=s;
	int l=k,r=K,mid,t=k-1;
	while (l<=r)
	{
		mid=(l+r)>>1;
		if (C[k]-C[mid+1]<=m) t=mid,l=mid+1;
		else r=mid-1;
	}
	C[k]+=s;
	return t+1;
}

int main()
{
	while (1)
	{
		scanf("%d%d%d",&N,&M,&K);
		if (!N) break;
		for (int i=1;i<=N;i++) scanf("%d",A+i);
		for (int i=1;i<=K;i++) scanf("%d",B+i);
		C[K+1]=0;
		for (int i=K;i;i--) C[i]=C[i+1]+B[i];
		memset(F,0xff,sizeof F);
		upd(1,M,1,0);
		ans=0;
		for (int i=1;i<=N;i++)
			for (int j=0;j<=M;j++)
			if (F[i][j]!=-1)
			{
				k=Calc(F[i][j],G[i][j],A[i]);
				if (k==F[i][j]) upd(i+1,j,k,G[i][j]+A[i]);
				else upd(i+1,j,k,0);
				if (!j) continue;
				k=Calc(F[i][j],G[i][j],A[i]<<1);
				if (k==F[i][j]) upd(i+1,j-1,k,G[i][j]+A[i]*2);
				else upd(i+1,j-1,k,0);
			}
		printf("%d\n",ans);
	}
}

  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  2. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的