//首先可以想到，红的一定放在最后，因为此时怪兽已经有了各种debuff
//所以我们用dp[i][j]表示在第i个位置，放了j个蓝法师的最大伤害，判断在当前放蓝法师还是绿法师更优，更新答案
//最后对于每种情况，把红法师加上去
//于是就可以n方过掉
#include<iostream>
using namespace std;
long long dp[1030][1030];
int main()
{
    int n;
    long long r,g,b,t,i,j,maxn;
    cin>>n>>r>>g>>b>>t;
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=i;j++)
         {
            if(j)
             dp[i][j]=max(dp[i][j],dp[i-1][j-1]+(t+b*(j-1))*g*(i-j));
            if(j<i)
             dp[i][j]=max(dp[i][j],dp[i-1][j]+(t+b*j)*g*(i-j-1));
         }
    }
    maxn=t*n*r;
    for(i=1;i<=n;i++)
     for(j=0;j<=i;j++)
      maxn=max(maxn,dp[i][j]+r*(n-i)*(t+b*j)+g*(i-j)*(n-i)*(t+b*j));
    cout<<maxn;
    return 0;
}

显然是先减速和下毒完以后再进红塔比较赚，所以红塔一定全部放在最后。用f[i][j]表示前i个塔里有j个蓝塔时，走过第i个塔后的累计伤害值，最后加上后面的红塔的全部伤害来更新答案。

#include<iostream>
using namespace std;
long long n,R,G,B,T,ans,f[1025][1025];//now at i,total j blue,else all red
int main()
{
    cin>>n>>R>>G>>B>>T;
    for(int i=1;i<=n;i++)
       for(int j=0;j<=i;j++)
       {
          if(i>j)   f[i][j]=f[i-1][j]+(T+B*j)*(i-j-1)*G;//this one green
          if(j>0)   f[i][j]=max(f[i][j],f[i-1][j-1]+(T+B*j-B)*(i-j)*G);//this one blue
          ans=max(ans,f[i][j]+(n-i)*(T+B*j)*(R+(i-j)*G));//update ans
       }
    cout<<ans<<endl;
    return 0;
}

/*
好题啊~唯一的坑点在于
想到了答案会在Longlong类型内 但是没想到
输入的数据也要开longlong
害怕啊然后一直WA一半的点然而却找不出错来
首先窝们玩过游戏的都知道
如果有减速,持续伤害,一次伤害的
那么肯定把一次伤害的放在最后面最优
因为这样能让持续性的伤害最大化
那么我们定义f[i][j]表示放i个蓝j个绿的最大伤害
这里的伤害不算上红色的伤害
那么自然很明显有初值
d[0, 0]:=0; {没有法师}
d[0, 1]:=0; {只放一个绿法师}
d[0, j]:=d[0, j-1]+(j-1)*g*t;(1<=j<=n)
{不放蓝法师，在前j个位置放绿法师的(最大)伤害}
d[i, 0]:=0;(1<=i<=n) {不放绿法师，在前i个位置放置蓝法师，伤害均为零}
那么状态转移方程也很容易出来
f[i][j]=max(f[i-1][j]+((i-1)*b+t)*g*j,f[i][j-1]+(i*b+t)*g*(j-1));
最后寻找答案的时候
应该枚举所有的f[i][j]然后剩下的就是放红色的法师了
计算出最大值就好了~
即max(ans,f[i][j]+(n-i-j)*(r+g*j)*(t+b*i))
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1028;
long long f[MAXN][MAXN];//f[i][j]表示放i个蓝j个绿的最大伤害
long long n,r,g,b,t;
long long ans=-1;

void init(){cin>>n>>r>>g>>b>>t;}

int main()
{
init();
for(int j=2;j<=n;j++)
f[0][j]=f[0][j-1]+(j-1)*g*t;
for(int i=1;i<=n;i++)
for(int j=0;j<=n-i;j++)
{
if(j>0)
f[i][j]=max(f[i-1][j]+((i-1)*b+t)*g*j,f[i][j-1]+(i*b+t)*g*(j-1));
else
f[i][j]=f[i-1][j]+((i-1)*b+t)*g*j;
ans=max(ans,f[i][j]+(n-i-j)*(r+g*j)*(t+b*i));
}
cout<<ans<<endl;
return 0;
}

这题有毒啊，想到了答案要longlong结果输入数据也要longlong，服了服了

除了对边界的处理有点坑，还是道不错的dp题。具体思想很漂亮，有点两种法师更新时互相结算对方因为自己决策的所有增加量，巧妙的维护了后效性。
代码贴出来吧。dp[i][j]表示前i个放j个蓝塔（减速），前面所有伤害的结算值（不算红的）。最后再加上红的。
```c++
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll R, G, B, N, T;
ll dp[1030][1030];

ll dfs(ll i, ll j) // 前i放j个蓝的
{
if (i == 0 && j == 0) return 0;
if (i <= 0) return -100000ll;
if (dp[i][j] != -1) return dp[i][j];
// printf("%d %d -- %d %d\n", i, j, dfs(i+1, j+1) + (i-j)*G*B*(N-i),
// dfs(i+1, j) + G*(N-i));
dp[i][j] = -100000;
if (dfs(i-1, j) >= 0)
dp[i][j] = dfs(i-1, j) + G*(N-i)*(T+j*B);
if (j >= 1 && dfs(i-1, j-1) >= 0)
dp[i][j] = max(dfs(i-1, j-1) + (i-j)*G*B*(N-i),dp[i][j]);
return dp[i][j];
}

int main()
{
cin >> N >> R >> G >> B >> T;
for (int i = 0; i <= N; i++)
for (int j = 0; j <= N; j++)
dp[i][j] = -1;
ll maxx = 0;
for (ll i = 0; i <= N; i++) {
for (ll j = 0; j <= i; j++) {
maxx = max(maxx, dfs(i, j) + (j*B+T)*R*(N-i));
}
//puts("");
}
cout << maxx << endl;
return 0;
}
```

用动规或贪心（吧），反正我用了动规。用f[i,j]表示放了i个绿塔，j个蓝塔的能造成的最大伤害。
PascalAC代码如下：
var i,j:longint;
n,r,g,b,t,x1,x2,ans:int64;
f:array[-1..1025,-1..1025] of int64;
function max(a,b:int64):int64;
begin
if a>b then exit(a) else exit(b);
end;
begin
readln(n,r,g,b,t);
f[0,0]:=r*n*t;
ans:=f[0,0];
for i:=0 to n do
for j:=0 to n do
if (i+j<=n)and((i<>0)or(j<>0)) then
begin
x1:=0; x2:=0;
if i-1>=0 then x1:=f[i-1,j]+(n-i-j)*(t+b*j)*g-r*(t+j*b);
if j-1>=0 then x2:=f[i,j-1]+(n-i-j)*(r+i*g)*b-r*(t+(j-1)*b);
f[i,j]:=max(x1,x2);
if f[i,j]>ans then ans:=f[i,j];
end;
writeln(ans);
end.

program v1417;
var f,ff:array[-1..1030] of int64;
i,j:longint;
n,r,g,b,t,m:int64;
function max(p,q:int64):int64;
begin
if p>q then exit(p) else exit(q);
end;
begin
readln(n,r,g,b,t);
m:=0;
for i:=1 to n do
begin
ff:=f;
for j:=0 to i do
begin
if j=i then f[j]:=ff[j-1]+(j-1)*g*t
else if j=0 then f[j]:=0
else f[j]:=max(ff[j-1]+(j-1)*g*(t+(i-j)*b),ff[j]+j*g*(t+(i-j-1)*b));
m:=max(m,f[j]+(n-i)*(r+j*g)*(t+(i-j)*b));
end;
end;
writeln(m);
end.
acacacacacacac

program v1417;
var f,ff:array[-1..1030] of int64;
i,j:longint;
n,r,g,b,t,m:int64;
function max(p,q:int64):int64;
begin
if p>q then exit(p) else exit(q);
end;
begin
readln(n,r,g,b,t);
m:=0;
for i:=1 to n do
begin
ff:=f;
for j:=0 to i do
begin
if j=i then f[j]:=ff[j-1]+(j-1)*g*t
else if j=0 then f[j]:=0
else f[j]:=max(ff[j-1]+(j-1)*g*(t+(i-j)*b),ff[j]+j*g*(t+(i-j-1)*b));
m:=max(m,f[j]+(n-i)*(r+j*g)*(t+(i-j)*b));
end;
end;
writeln(m);
end.

var
f:array[0..1024,0..1024]of qword;
i,j:longint;
tot,max,n,r,b,g,t:qword;

begin
readln(n,r,g,b,t); tot:=0;
fillchar(f,sizeof(f),0);

for i:=0 to n do
for j:=0 to n-i do
begin
if i>0 then
if f[i,j]<f[i-1,j]+g*j*(t+(i-1)*b) then
f[i,j]:=f[i-1,j]+g*j*(t+(i-1)*b);

if j>0 then
if f[i,j]<f[i,j-1]+g*(j-1)*(t+i*b) then
f[i,j]:=f[i,j-1]+g*(j-1)*(t+i*b);

tot:=f[i,j]+(n-i-j)*(g*j+r)*(t+i*b);
if tot>max then max:=tot;
end;

writeln(max);
end.
1. 比较坑人的地方，统统都是要INT64的= =
2. 明显红色在最后，前面放蓝绿
3. 楼下好评
4.我的DP是F数组记录没有红塔是最大的输出功效，i枚举蓝的，j枚举绿的，最后再算上红色的

首先，红色打击的肯定放在最后的，而蓝色和绿色到底怎么放不知道，所以要枚举（即DP）；问题转换成：m（0《m《=n）个里蓝色放几个绿色放几个，每种有放于不放。后面（n-m）个放红色。所以DP方程就出来了：F[I,J,K]表示前i个，蓝j个，绿k个，因为j+k=i所以只要开两维。
for i:=2 to n do
for j:=0 to i-1 do
begin
f[i,j+1]:=max(f[i,j+1],f[i-1,j]+xx1;
f[i,j]:=max(f[i,j],f[i-1,j]+xx2;
ans:=max(ans,f[i,j+1]+xx3;
ans:=max(ans,f[i,j]+xx4;
end;
writeln(ans);
end.
L.G.S-国庆节

令前i个格子里放j个蓝塔，怪物走到第i格的最大伤害
f[i][j]=Max{
f[i-1][j]+(i-j-1)*(B*j+T)*G,
f[i-1][j-1]+(i-j)*(B*(j-1)+T)*G
}

测试数据 #0: Accepted, time = 15 ms, mem = 9944 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 9944 KiB, score = 10
测试数据 #2: Accepted, time = 31 ms, mem = 9940 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 9944 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 9940 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 9940 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 9936 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 9936 KiB, score = 10
测试数据 #8: Accepted, time = 31 ms, mem = 9944 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 9940 KiB, score = 10
Accepted, time = 169 ms, mem = 9944 KiB, score = 100

为什么 要用int64？

100%的数据满足1

此题#2...

...又是对题目范围估计有误

第一次交40分.1点WA,原来要用int64...

而且最开始做时,每次循环都执行g:=f(1024^2大的数组),结果弄超时(剩下5个点)了.......

---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--

解题报告:

由于毒塔和冰塔都是加Buff的,而火塔是即时掉血的,所以很容易发现,要使掉血最多,则火塔应放最后面.如果前面的毒塔数和冰塔数都确定的话呢,最大掉血即为经过火塔前面的塔所掉的最大血值,满足无后效性.

故可以冰/毒塔的总数k作为阶段划分(因为这两种塔只能在最前面),状态为冰塔数和毒塔数,经过这些塔后(k个塔)的最大伤害值.

状态转移方程:f[k,i,j]=max{f[k-1,i-1,j]+(b*(i-1)+t)*d*j,f[k-1,i,j-1]+(b*i+t)*d*(j-1)}(i-1>0,j-1>0,i+j=k);

由于k单调递增,且i+j=k,故方程可简化为:

f=max{f+(b*(i-1)+t)*d*j,f+(b*i+t)*d*(j-1)}(i-1>0,j-1>0,i+j=k);

所以最大掉血值

ans=max{f+(b*i+t)*(n-i-j)*(d*j+h))}(i>=0,j>=0,i+j=0 then f:=f+(b*(i-1)+t)*d*j;

if j-1>=0 then f:=max(f,f+(b*i+t)*d*(j-1));

ans:=max(ans,f+(b*i+t)*(n-k)*(d*j+h));

end;

end;

writeln(ans);

end;

时间复杂度O(n^2),但是却

Accepted 有效得分：100 有效耗时：366ms

大数不断做乘法果然费时...

对样例的解释：

1 2 3 4 5

G B B R R

一定是最后再放R魔法师

DP求解B,G的放置方法，求最优解

注意的问题：读入的N,R,G,B,T和数组还有输出的结果都需要用int64

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 9ms

├ 测试数据 08：答案正确... 41ms

├ 测试数据 09：答案正确... 41ms

├ 测试数据 10：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：132ms

数据有点变态！

其他的 easy！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 25ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：59ms

400通过mark

求样例解释

82是如何得出的

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：27ms

输入也要用int64……

program v1417;

var f,ff:array[-1..1030] of int64;

i,j:longint;

n,r,g,b,t,m:int64;

function max(p,q:int64):int64;

begin

if p>q then exit(p) else exit(q);

end;

begin

readln(n,r,g,b,t);

m:=0;

for i:=1 to n do

begin

ff:=f;

for j:=0 to i do

begin

if j=i then f[j]:=ff[j-1]+(j-1)*g*t

else if j=0 then f[j]:=0

else f[j]:=max(ff[j-1]+(j-1)*g*(t+(i-j)*b),ff[j]+j*g*(t+(i-j-1)*b));

m:=max(m,f[j]+(n-i)*(r+j*g)*(t+(i-j)*b));

end;

end;

writeln(m);

end.

很短小 很精悍

var i,j,m,k:longint;

max,r,g,b,t,n,l,o,p:int64;

f:array[-1..2000,-1..2000] of int64;

begin

readln(n,r,g,b,t);

fillchar(f,sizeof(f),0);

for i:=1 to n-1 do

f[0,i]:=f[0,i-1]+(i-1)*t*g;

max:=0;

for i:=1 to n-1 do

for j:=0 to n-i-1 do

begin

l:=f+(t+(i-1)*b)*j*g;

o:=f+(t+i*b)*(j-1)*g;

if l>o then f:=l else f:=o;

p:=f+(t+i*b)*(r+g*j)*(n-i-j);

if p>max then

max:=p;

end;

writeln(max);

end.