网站建设明薇通网络服务好,小型创意电子产品设计,淘客推广佣金,电子版个人简历模板正题 题目大意 nnn个武器(n≤2n\leq2n≤2)#xff0c;mmm个符文
符文1:直接改变一个武器的攻击力(最多一个)
符文2:增加一个武器的攻击力
符文3:使一个人的武器攻击力翻若干倍
求武器攻击力乘积最大#xff0c;输出答案的自然对数。 解题思路
首先log(ab)log(a)log(b)lo…正题 题目大意
nnn个武器(n≤2n\leq2n≤2)mmm个符文
符文1:直接改变一个武器的攻击力(最多一个)
符文2:增加一个武器的攻击力
符文3:使一个人的武器攻击力翻若干倍
求武器攻击力乘积最大输出答案的自然对数。 解题思路
首先log(ab)log(a)log(b)log(ab)log(a)log(b)log(ab)log(a)log(b)
然后乘积的就不管最后答案加上就好了我们只考虑前两种
n1n1n1时直接暴力枚举选多少加攻击的。
n2n2n2时我们考虑dpdpdp。首先我们肯定选大的主要考虑哪个加在哪个上面。
fi,jf_{i,j}fi,j表示前iii个符文第一个武器攻击力为jjj时的武器威力乘积。我们维护一下前缀和就可以计算第二个武器的攻击力
若加在第一个符文上fi,jmin{fi−1,j−addiaddi∗(sumi−j)}f_{i,j}min\{f_{i-1,j-add_i}add_i*(sum_i-j)\}fi,jmin{fi−1,j−addiaddi∗(sumi−j)} 若加在第二个符文上fi,jmin{fi−1,jaddi∗j}f_{i,j}min\{f_{i-1,j}add_i*j\}fi,jmin{fi−1,jaddi∗j}
然后转移。
之后暴力枚举加的符文选几个其他都选乘的。
对于符文1直接处理333次 codecodecode
#includecstdio
#includealgorithm
#includecstring
#includecmath
using namespace std;
const int N110;
int n,m,k,add[N],sum[N],cnt1,cnt2,mul[N];
int fff,f[N][N*2000],maxs[N],a1,a2;
double ans,summ[N];
bool cmp(int x,int y)
{return xy;}
int main()
{//freopen(data.in,r,stdin);//freopen(data.out,w,stdout);scanf(%d%d%d,n,m,k);scanf(%d,a1);if(n2) scanf(%d,a2);for(int i1;im;i){int x,t;scanf(%d%d,t,x);if(t1) fffx;if(t2) add[cnt1]x;if(t3) mul[cnt2]x;}sort(add1,add1cnt1,cmp);sort(mul1,mul1cnt2,cmp);sum[0]a1a2;for(int i1;ik;i){summ[i]summ[i-1]log(mul[i]);sum[i]sum[i-1]add[i];}if(n1){for(int i0;ik;i){ansmax(ans,log(sum[min(i,cnt1)])summ[min(k-i,cnt2)]);if(i!kfff)ansmax(ans,log(sum[min(i,cnt1)])summ[min(k-i-1,cnt2)]);}printf(%.3lf\n,ans);return 0;}memset(f,0xcf,sizeof(f));f[0][a1]a1*a2;for(int i0;icnt1;i){for(int ja1;jsum[i];j){f[i1][j]max(f[i][j]add[i1]*j,f[i1][j]);f[i1][jadd[i1]]max(f[i][j]add[i1]*(sum[i]-j),f[i1][jadd[i1]]);maxs[i]max(maxs[i],f[i][j]);}}for(int u0;uk;u){int mumin(k-u,cnt2);ansmax(ans,log(maxs[min(u,cnt1)])summ[mu]);}if(fff){k--;sum[0]fffa2;for(int i1;ik;i)sum[i]sum[i-1]add[i];memset(f,0xcf,sizeof(f));memset(maxs,0,sizeof(maxs));f[0][fff]fff*a2;for(int i0;ik;i){for(int jfff;jsum[i];j){f[i1][j]max(f[i][j]add[i1]*j,f[i1][j]);f[i1][jadd[i1]]max(f[i][j]add[i1]*(sum[i]-j),f[i1][jadd[i1]]);maxs[i]max(maxs[i],f[i][j]);}}for(int u0;uk;u){int muk-u;ansmax(ans,log(maxs[u])summ[mu]);}sum[0]a1fff;for(int i1;ik;i)sum[i]sum[i-1]add[i];memset(f,0xcf,sizeof(f));memset(maxs,0,sizeof(maxs));f[0][a1]a1*fff;for(int i0;ik;i){for(int ja1;jsum[i];j){f[i1][j]max(f[i][j]add[i1]*j,f[i1][j]);f[i1][jadd[i1]]max(f[i][j]add[i1]*(sum[i]-j),f[i1][jadd[i1]]);maxs[i]max(maxs[i],f[i][j]);}}for(int u0;uk;u){int muk-u;ansmax(ans,log(maxs[u])summ[mu]);}}printf(%.3lf,ans);
}
