题目

游戏的战斗系统一般都需要平衡性评估，尤其是伤害输出能力。我们需要在各种战斗规则下，计算角色的最大伤害输出能力。以下题目都是单个或多个角色一起攻击单个目标，不考虑目标血量，只考虑伤害能力。
（1）两个角色A和B，攻击冷却时间分别为k1，k2秒，每次攻击能分别造成d1，d2的伤害。只要未在冷却中，角色可以自由选择攻击的时机，但只能在整数秒发动攻击。战斗时长总长为t秒。k1,k2,d1,d2,t都是正整数。战斗中有额外的规则：若两个角色在同一时刻一起攻击，则每个角色造成的伤害额外提升x%,x>0。请编写一段代码，计算两个角色在整场战斗中一共最多能造成多少伤害。
（2）两个角色A和B，攻击冷却时间分别为k1，k2秒，每次攻击能分别造成d1，d2的伤害。只要未在冷却中，角色可以自由选择攻击的时机，但只能在整数秒发动攻击。战斗时长总长为t秒。k1,k2,d1,d2,t都是正整数。角色A拥有增加伤害的技能：若B单独攻击时，A会清除当前冷却时间跟随B一起攻击，攻击之后A重新开始计算冷却时间。请编写一段代码，计算两个角色在整场战斗中一共最多能造成多少伤害。
（3）两个角色A和B，攻击冷却时间分别为k1，k2秒，每次攻击能分别造成d1，d2的伤害。只要未在冷却中，角色可以自由选择攻击的时机，但只能在整数秒发动攻击。战斗时长总长为t秒。k1,k2,d1,d2,t都是正整数。角色A拥有增加伤害的技能：只要己方攻击一次（A攻击或B攻击或者AB一起攻击），则A在接下来的战斗中伤害增加x%,x>0，该效果可一直叠加到战斗结束。请编写一段代码，计算两个角色在整场战斗中一共最多能造成多少伤害。

题解

第一小题

在经过思考之后，我觉得该题有些类似01背包问题，所以选择动态规划算法来解决这个问题。
（1）确定dp数组以及对应的下标含义
dp[i][0]:第i秒时总和伤害最高时，玩家A能打出的伤害为多少。
dp[i][1]:第i秒时总和伤害最高时，玩家B能打出的伤害为多少。
dp[i][2]:第i秒时加入额外条件后的总和最高伤害。
（2）递推公式
dp[i][0]=max(dp[i-1][0],dp[i-k1][0]+d1);//只有玩家A时所能打出的最高伤害。
dp[i][1]=max(dp[i-1][1],dp[i-k2][1]+d2);//只有玩家B时所能打出的最高伤害。
dp[i][2]=max(dp[i-1][2],dp[i-k1]+dp[i-k2]+(d1+d2)*(1+x));//当前两个玩家一起攻击时的最高伤害。
if(dp[i][0]+dp[i][1]<dp[i][2])//比较获得总和伤害最大的值，然后更新不统一的数。
{
dp[i][0]=dp[i-k1][0]+d1*(1+x);
dp[i][1]=dp[i-k2][1]+d2*(1+x);
}
else
{
dp[i][2]=dp[i][0]+d[i][1];
}
（3）初始化
直接全部初始化为0即可，让代码自行推算。
（4）遍历顺序
从0到背包大小t-1即可。
（5）举例
当k1=2,k2=3,d1=5,d2=10,t=10,x=1时，
dp数组变化如下：
0 1 2 3 4 5 6 7 8 9
dp[i][0]:10 10 20 20 30 30 40 40 50 50
dp[i][1]:20 20 20 40 40 40 60 60 60 80
dp[i][2]:30 30 40 60 70 70 100 100 110 130

C++代码如下：

	int main(int argc, char* argv[])

{
	//参数
	int k1=2,k2=3;
	int d1=5,d2=10;
	int t=10;
	int x=1;
	//dp数组
	vector<vector<int>> dp(t,vector<int>(3,0));
	//遍历
	for(int i=0;i<t;i++)
	{
		//只有玩家A时所能打出的最高伤害
		dp[i][0]=max(i-1>=0?dp[i-1][0]:0,(i-k1>=0?dp[i-k1][0]:0)+d1);
		//只有玩家B时所能打出的最高伤害
		dp[i][1]=max(i-1>=0?dp[i-1][1]:0,(i-k2>=0?dp[i-k2][1]:0)+d2);
		//当前两个玩家一起攻击时的最高伤害。
		dp[i][2]=max(i-1>=0?dp[i-1][2]:0, (i-k1>=0?dp[i-k1][0]:0)+(i-k2>=0?dp[i-k2][1]:0)+(d1+d2)*(1+x));
		//更新总和最大值,统一三个值,方便后面的计算，
		//其实也是将附加条件的计算结果，赋给dp[i][0],dp[i][1],
		//让附加条件的触发次数不止一次。
		if(dp[i][0]+dp[i][1]<dp[i][2])
		{
			dp[i][0]=i-k1>=0?dp[i-k1][0]+d1*(1+x):d1*(1+x);
			dp[i][1]=i-k2>=0?dp[i-k2][1]+d2*(1+x):d2*(1+x);

		}
		else
		{
			dp[i][2]=dp[i][0]+dp[i][1];
		}

		
	}
	//输出dp数组
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<t;j++)
		{
			cout<<dp[j][i]<<" ";
		}
		cout<<endl;
	}
	
	cout<<dp[t-1][2]<<endl;
    return 0;

}