记忆深刻......打铁没做出来的题

题意 ：

打怪，有 A 的攻击力，有 D 的成长，初始均为 0，有 n 轮。

同时有三个数组 a[1:n],b[1:n],c[1:n]

对于每一轮：

首先，攻击力永久性成长 A=A+D；然后，在下面三个选择中选择一种行为：

①、发起进攻，产生 A+ai的伤害。

②、增加成长 D=D+bi。

③、永久性增加攻击力 A=A+ci。问产生最大总伤害为多少

思路：

逆向DP，DP [ i ]代表的是从第i天到第n天产生的最大伤害，转移方程分析一下：

如果 这一天选择 ① 那么 对后面的影响是伤害增加 ai，选择②对后面影响的是攻击的那些天数伤害都增加 ( bi * （j-i））

选择③对后面的影响是，增加伤害为攻击的天数 * c[ i ],那么dp 需要增加两个变量 ，一个是方便计算选择②的情况

增加一个攻击了的天数下标和，另一个是 当前攻击的天数数目和，初始值为 dp[ n ] [ 1 ] [ n ] =  a [ n ] 详见代码：

#include
     
      using namespace std;#define maxn 111#define ll long longll t,n,a[maxn],b[maxn],c[maxn];ll dp[3][maxn][maxn*maxn/2],ans;int main(){    scanf("%lld",&t);    while(t--)    {        ans=0;        memset(dp,0,sizeof(dp));        scanf("%lld",&n);        for(int i=1; i<=n; i++)            scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);        dp[n&1][1][n]=a[n];        for(int i=n-1; i>=1; i--)        {            for(int j=1; j+i<=n; j++)            {                int low = (i+i+j)*(j-1)/2+n;                int up = (n+n-(j-1))*j/2;                for(int k=low; k<=up; k++)                {                    dp[i&1][j+1][k+i]=max(dp[i&1][j+1][k+i],dp[(i+1)&1][j][k]+a[i]);                    dp[i&1][j][k]=max(dp[i&1][j][k],dp[(i+1)&1][j][k]+(k-j*i)*b[i]);                    dp[i&1][j][k]=max(dp[i&1][j][k],dp[(i+1)&1][j][k]+j*c[i]);                }            }        }        for(int j=1; j<=n; j++)            for(int k=n; k<=5050; k++)                ans=max(ans,dp[1][j][k]);        printf("%lld\n",ans);    }    return 0;}