P1412 经营与开发【洛谷算法习题】

P1412 经营与开发网页链接P1412 经营与开发题目描述4 X 4X4X概念体系是指在 PC 战略游戏中一种相当普及和成熟的系统概念得名自4 44个同样以 EX 为开头的英语单词。eXplore \verb!eXplore!eXplore探索eXpand \verb!eXpand!eXpand拓张与发展eXploit \verb!eXploit!eXploit经营与开发eXterminate \verb!eXterminate!eXterminate征服——维基百科今次我们着重考虑 exploit 部分并将其模型简化你驾驶着一台带有钻头初始能力值w ww的飞船按既定路线依次飞过n nn个星球。星球笼统的分为2 22类资源型和维修型。p pp为钻头当前能力值资源型含矿物质量a i a_iai​若选择开采则得到a i × p a_i\times pai​×p的金钱之后钻头损耗k % k\%k%即p ← p × ( 1 − 0.01 k ) p\gets p\times (1-0.01k)p←p×(1−0.01k)维修型维护费用b i b_ibi​若选择维修则支付b i × p b_i\times pbi​×p的金钱之后钻头修复c % c\%c%即p ← p × ( 1 0.01 c ) p\gets p\times (10.01c)p←p×(10.01c)。注维修后钻头的能力值可以超过初始值你可以认为是翻修 升级金钱可以透支。请作为舰长的你仔细抉择以最大化收入。输入格式第一行4 44个整数n , k , c , w n,k,c,wn,k,c,w。以下n nn行每行2 22个整数t y p e , x \mathrm{type},xtype,x。t y p e \mathrm{type}type为1 11则代表其为资源型星球x xx为其矿物质含量a i a_iai​t y p e \mathrm{type}type为2 22则代表其为维修型星球x xx为其维护费用b i b_ibi​输出格式一个实数保留2 22位小数表示最大的收入。输入输出样例 #1输入 #15 50 50 10 1 10 1 20 2 10 2 20 1 30输出 #1375.00说明/提示数据范围及约定对于30 % 30\%30%的数据n ≤ 100 n \le 100n≤100另有20 % 20\%20%的数据n ≤ 1000 n \le 1000n≤1000k 100 k100k100对于100 % 100\%100%的数据n ≤ 100000 n \le 100000n≤1000000 ≤ k , c , w , a i , b i ≤ 100 0 \le k,c,w,a_i,b_i \le 1000≤k,c,w,ai​,bi​≤100保证答案不超过10 9 10^9109。解题思路本题是线性动态规划 系数归一化的经典优化题核心利用钻头能力值的乘法缩放特性将高维状态压缩为单变量通过倒序递推实现线性时间求解。核心性质收益与钻头能力线性相关所有操作对钻头能力值的修改均为乘法缩放开采后乘以( 1 − 0.01 k ) (1-0.01k)(1−0.01k)维修后乘以( 1 0.01 c ) (10.01c)(10.01c)。因此后续所有收益与当前钻头能力值呈严格线性关系——若钻头能力变为原来的k kk倍后续最大收益也会变为原来的k kk倍。基于该性质无需记录钻头能力的具体数值只需维护「钻头能力为1单位时后续能获得的最大收益」即可通过系数缩放推导任意钻头能力下的最优收益将状态维度从二维压缩为一维。倒序动态规划从最后一个星球向前倒序递推变量ans表示处理到当前星球时钻头能力为1单位从当前星球到末尾能获得的最大收入。资源型星球type1不开采钻头能力不变后续收益保持为ans。开采立即获得a i a_iai​的单位收益钻头能力变为原来的( 1 − 0.01 k ) (1-0.01k)(1−0.01k)倍后续收益缩放为a n s × ( 1 − 0.01 k ) ans \times (1-0.01k)ans×(1−0.01k)总收益为a i a n s × ( 1 − 0.01 k ) a_i ans \times (1-0.01k)ai​ans×(1−0.01k)。取两者最大值更新当前ans。维修型星球type2不维修钻头能力不变后续收益保持为ans。维修立即支付b i b_ibi​的单位成本钻头能力变为原来的( 1 0.01 c ) (10.01c)(10.01c)倍后续收益缩放为a n s × ( 1 0.01 c ) ans \times (10.01c)ans×(10.01c)总收益为a n s × ( 1 0.01 c ) − b i ans \times (10.01c) - b_ians×(10.01c)−bi​。取两者最大值更新当前ans。结果计算初始钻头能力为w ww因此最终总收益为ans * w保留两位小数输出即可。算法时间复杂度为O ( n ) O(n)O(n)空间复杂度为O ( n ) O(n)O(n)仅存储星球信息完美适配n ≤ 10 5 n \le 10^5n≤105的数据规模。总结核心逻辑利用钻头能力的乘法缩放特性将收益归一化到单位钻头能力下通过倒序递推逐个决策每个星球的最优选择最终乘以初始钻头能力得到答案。关键操作线性关系推导、倒序DP设计、两类星球的状态转移、浮点精度处理。效率保障仅一次线性遍历无嵌套循环常数级额外变量十万级数据可毫秒级完成。代码简要说明数据存储数组t存储星球类型g存储资源型星球的矿物量l存储维修型星球的维护费用。倒序递推从第n个星球倒序遍历到第1个根据星球类型分别计算操作与不操作的收益取最大值更新ans单位钻头的后续最大收益。结果输出将单位收益乘以初始钻头能力w使用printf格式化保留两位小数输出。输入优化关闭流同步加速输入适配十万级数据的读取效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;doublen,k,c,w;doubleg[100001],l[100001];ll t[100001];doubleans;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnkcw;for(ll i1;in;i){cint[i];if(t[i]1)cing[i];elsecinl[i];}for(ll in;i1;i--){if(t[i]1)ansmax(ans*(1-0.01*k)g[i],ans);elseansmax(ans*(10.01*c)-l[i],ans);}printf(%.2lf,ans*w);return0;}