2015
04-14

# Sacred Warrior

Sacred Warrior is a hero in DotA and his name is Huskar. The Sacred Warrior’s abilities revolve around shortening his own lifespan to spear his foes to burinng pieces.When we control the Sacred Warrior , we always want to give our enemies the most damage.So to simplify the problem,let’s consider the Sacred Warrior’s two skills as below:

(1) Burning Spear

When the Sacred Warrior use the Burning Spear to attack his enemy, follow things will happen in order in the current second:

1.the enemy gets physical hurt by a normal attatk.

2.if the enemy’s burning degree BD is greater than zero,the enemy will gets BD*FI damage points.(at the beginning,the enemy’s burning degree is zero).

3.the enemy’s burning degree +1.

4.the remanent burning time become 6.

5.the Sacred Warrior’s HP decrease by D. The Sacred Warrior can not kill himself(don’t ask me why),that is,when the Sacred Warrior’s HP is less than or equal to D, the Sacred Warrior can not use Burning Spear!

When the Sacred Warrior use a single normal attack instead of Burning Spear, follow things will happen in order in the current second:

1.the enemy gets physical hurt by the normal attack.

2.if the enemy’s burning degree BD is greater than zero,the enemy will gets BD*FI damage points.(at the beginning,the enemy’s burning degree is zero).

3.the remanent burning time decrease by 1.

4.if the remanent burning time is zero, then the enemy’s burning degree become zero.

(2) Berserk’s blood

The Sacred Warrior’s base attack is A.

Whenever the Sacred Warrior’HP reduce R ,his attack will increase U, it means the Sacred Warrior will get ((HS-HC) / R)*U extra attack.(round down for division, hs is the original HP and the hc is the current HP).

The normal attack NA is the sum of base attack and extra attack.

The enemy has a defence degree DEFi and it change every second(the reason is complicated,such as Weave,Meld,Gush,Natural Order,Mekansm and so on).Whenever the enemy is attacked by a normal attack(a single normal attack or the first part of Burning Spear), if the enemy’s defence degree is greater than the normal attack, the enemy won’t get any physical hurt(but the burning effect is still effective), otherwise the enemy will get NA-DEFi damage.(NA is the current normal attack and the DEFi is the current defence degree).

Every second The Sacred Warrior can choose using a single normal attack or Burning Spear to attack the enemy. But in order to make the most damage and lose too much HP is obviously not wise. So we use a evaluation function F=C – (HS-HE)*P to evaluate the fight. (hs is the original HP and the he is the HP after last second, C is the total damage he cause).Can you find the maximal F ?

The first line contains a single positive integer N( N <= 20 ), indicates the number of test cases.

For each test case:

The first line contains eight integers T , HS , A , R , U , D , FI , P , T is the total time in seconds and the others is as described above.

The second line contains T integers , the i-th integer is the defence degree DEFi in i-th second.

0< T < 200 , 0< HS < 100 , 0 < A < 5000 , 0< R < HS , 3<= D <= 10 , 0 <= U , FI , P <1000

0 <= DEFi <3000

The first line contains a single positive integer N( N <= 20 ), indicates the number of test cases.

For each test case:

The first line contains eight integers T , HS , A , R , U , D , FI , P , T is the total time in seconds and the others is as described above.

The second line contains T integers , the i-th integer is the defence degree DEFi in i-th second.

0< T < 200 , 0< HS < 100 , 0 < A < 5000 , 0< R < HS , 3<= D <= 10 , 0 <= U , FI , P <1000

0 <= DEFi <3000

2
5 10 5 3 2 3 2 1
0 0 0 0 0
5 10 1 7 1 3 5 1
2 2 2 2 2

Case #1: 52
Case #2: 36
Hint
In the first case:

The Sacred Warrior use burning spear in second 1,2 and 3, use single normal attack in second 4 and 5.

TIME 0 1 2 3 4 5HP 10 7 4 1 1 1defence 0 0 0 0 0 0

normal atk 0 5 7 9 11 11burning atk 0 0 2 4 6 6

So F=(5+7+9+11+11+0+2+4+6+6)-(10-1)*1=52;

In the second case:

The Sacred Warrior use burning spear in second 1,2 and 3, use single normal attack in second 4 and 5.

TIME 0 1 2 3 4 5HP 10 7 4 1 1 1defence 0 2 2 2 2 2

normal atk 0 1 1 1 2 2burning atk 0 0 5 10 15 15

Because every second the DEFi is greater than or equal to the normal attack, so the normal attack is complete invalid.

So F=(0+5+10+15+15)-(10-1)*1=36;
Cached at 2011-08-25 16:03:45.


#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;

#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define clr(a, b) memset(a, b, sizeof(a))
#define SZ(a) ((int)a.size())
#define PB push_back
#define MP make_pair
#define inf 0x3f3f3f3f
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;

#ifdef ecust
#define RR "%lld"
#else
#define RR "%I64d"
#endif

namespace acm {

int dp[2][220][10][220];
int T, HS, A, R, U, D, FI, P;
int des[300];
void update(int &a, int b) {
a = max(a, b);
}
void solve() {
scanf("%d%d%d%d", &T, &HS, &A, &R);
scanf("%d%d%d%d", &U, &D, &FI, &P);
forn(i, T)
scanf("%d", des + i + 1);
clr(dp, 0x3f);
forn(i, 2)
forn(j, 220)
forn(k, 10)
forn(l, 220)
dp[i][j][k][l] = -inf;
int now = 0;
dp[0][HS][0][0] = 0;
for (int tt = 1; tt <= T; ++tt) {

int fang = des[tt];
for (int i = 1; i <= HS; ++i) {
for (int j = 0; j <= 6; ++j) {
for (int k = 0; k <= T; ++k) {
if (dp[now][i][j][k] == -inf)
continue;
if (i > D) {
int add = A + (HS - i) / R * U;
if (add < fang)
add = 0;
else
add -= fang;
update(dp[now ^ 1][i - D][6][k + 1], dp[now][i][j][k]
+ add + FI * k);
}
int add = A + (HS - i) / R * U;
if (add < fang)
add = 0;
else
add -= fang;
if (j - 1 == 0)
update(dp[now ^ 1][i][j - 1][0], dp[now][i][j][k] + add
+ FI * k);
else if (j)
update(dp[now ^ 1][i][j - 1][k], dp[now][i][j][k] + add
+ FI * k);
else if (j == 0)
update(dp[now ^ 1][i][j][k], dp[now][i][j][k] + add);
}
}
}
now = now ^ 1;
}
int ans = -inf, ans2 = -inf;
forn(j, 220)
forn(k, 10)
forn(l, 220) {
if (dp[now ][j][k][l] != inf) {
update(ans, dp[now ][j][k][l] - (HS - j) * P);
//			update(ans2, dp[now ][j][k][l]);
}
}
printf("%d\n", ans);
}
void icpc() {
int nc, nn = 1;
scanf("%d", &nc);
while (nc--) {
printf("Case #%d: ", nn++);
solve();
}
}
}

int main() {
#ifdef ecust
freopen("in", "r", stdin);
#endif
acm::icpc();
//	cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
return 0;
}

1. 有一点问题。。后面动态规划的程序中
int dp[n+1][W+1];
会报错 提示表达式必须含有常量值。该怎么修改呢。。

2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。

3. int half(int *array,int len,int key)
{
int l=0,r=len;
while(l<r)
{
int m=(l+r)>>1;
if(key>array )l=m+1;
else if(key<array )r=m;
else return m;
}
return -1;
}
这种就能避免一些Bug
l,m,r
左边是l,m;右边就是m+1,r;