问题 B: 打怪
时间限制: 1 Sec 内存限制: 128 MB提交: 83 解决: 8
[提交] [状态] [命题人:admin]
题目描述
小M喜欢打怪兽。这天,她又在打怪兽。
经过了努力,她已经来到了最后的boss战,她已经知道自己可以有N个回合进行操作,每个回合可以进行下面若干种操作之一:
·执行一次攻击,第i个回合发动攻击,造成的伤害等于对boss造成当前的攻击力A与本回合攻击力di之和。
·使用一次能力,之后的每个回合开始时自己的攻击力A都会增加ai点。
·使用一次能力,使得自己当前的攻击力A增加bi点。
一开始小M的攻击为0,现在小M想要知道N个回合后小M对boss能够造成最多的伤害总量。
输入
第一行一个正整数N。接下来N行,每行三个正整数di,ai,bi。
输出
输出一行一个整数表示答案。
样例输入
2 3 1 2 3 1 2
样例输出
6
思路:暴力的话,考虑对每一个i有三种操作,所以是3
100
时间复杂度太高,所以适当剪枝。
对于一个i考虑当前攻击力ac和每回合要加的数t对后续的影响。另开一个数组记录
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll a[105],d[105],b[105]; ll f[105]; ll ans=0,n; void dfs(int step,ll ac,ll sum,ll t) { ac+=t; if(step>n) { ans=max(ans,sum); return; } int j=n-step+1; if(sum+ac*j+t*(j+1)*j/2<=f[step]&&f[step]!=0) return; f[step]=sum+ac*j+t*(j+1)*j/2; dfs(step+1,ac,sum+d[step]+ac,t); dfs(step+1,ac,sum,t+a[step]); dfs(step+1,ac+b[step],sum,t); } int main() { cin>>n; for(int i=1;i<=n;i++) { scanf("%lld%lld%lld",d+i,a+i,b+i); } dfs(1,0,0,0); cout<<ans; return 0; }