题目描述
米薇女王万万没有想到考德威尔男爵的真实意图。她的脑海里浮现出莱里亚的秀美山河,可惜再也回不去了。
不过所幸的是,她还有着军队和重整山河的勇气。雷纳德为米薇女王呈上了 nnn 块符文石。符文石可以帮助你更好的战斗。每个符文石拥有能量,米薇可以挑选类型相近的符文石融合并释放出能量。
形象的,我们可以把每个符文石 PiP_iPi 描述成一个二元组 (ai,bi)(a_i,b_i)(ai,bi) 。对于两个相邻的符文石 PiP_iPi 与 Pi+1P_{i+1}Pi+1,可以把他们融合为 (ai,bi+1)(a_i,b_{i+1})(ai,bi+1) 并释放出 ai+1∗bia_{i+1}*b_iai+1∗bi 的能量。融合完的符文石会替换掉原本的两个二元组,出现在他们的位置上。米薇希望把所有的 nnn 个符文石融合成 111 个符文石。你可以以任意顺序合并相邻的两个符文石。
幸运的是,米薇找到了一个法力通天的术士,在全部融合过程前你可以选择一段连续的区间将里面的符文石精炼。即把原本的一段二元组 (ai,bi)(a_i,b_i)(ai,bi) 乘 kkk 变为 (ai⋅k,bi⋅k)(a_i \cdot k,b_i \cdot k)(ai⋅k,bi⋅k)。当然你也可以不选择任何区间。注意此操作必须在初始状态进行。
她希望她释放的能量尽可能小并想知道这个值是多少。
你可以结合样例解释来理解题目。
提示
最优方案下,你可以选择区间 [1,2][1,2][1,2] 精炼。
原序列变为(1,2) (−2,−3) (3,4) (−3,5)(1,2)\ (-2,-3)\ (3,4)\ (-3,5)(1,2) (−2,−3) (3,4) (−3,5)
你可以合并 (−2,−3) (3,4)(-2,-3)\ (3,4)(−2,−3) (3,4) 释放出 −3∗3=−9-3*3=-9−3∗3=−9 点能量。
序列变为(1,2) (−2,4) (−3,5)(1,2)\ (-2,4)\ (-3,5)(1,2) (−2,4) (−3,5)
再合并(1,2) (−2,4)(1,2)\ (-2,4)(1,2) (−2,4) 释放出 −2∗2=−4-2*2=-4−2∗2=−4 点能量。
序列变为 (1,4) (−3,5)(1,4)\ (-3,5)(1,4) (−3,5)。
合并剩余符文石释放出 −12-12−12 点能量。序列最终剩下一个符文石 (1,5)(1, 5)(1,5)。
#include<iostream> #include<stdio.h> #include<cmath> #include<string.h> #include<algorithm> #define ll long long #define INF 0x3f3f3f3f using namespace std; ll dp[500050][3]; ll num[500050][2]; int main() { ll n,k; cin>>n>>k; for(int i=0; i<n; i++) { dp[i][0]=dp[i][1]=dp[i][2]=INF; cin>>num[i][0]>>num[i][1]; } dp[0][0]=INF; dp[0][1]=0; dp[0][2]=0; for(int i=1; i<n; i++) { //dp[i][0]代表乘k的段在当前二元组前面,[1]代表当前二元组乘了k,[2]表示k子段在后面 dp[i][0]=min(dp[i-1][1]+num[i-1][1]*k*num[i][0],dp[i-1][0]+num[i-1][1]*num[i][0]); dp[i][1]=min(dp[i-1][1]+num[i-1][1]*k*num[i][0]*k,dp[i-1][2]+num[i-1][1]*num[i][0]*k); dp[i][2]=dp[i-1][2]+(num[i-1][1]*num[i][0]); } cout<<min(dp[n-1][1],min(dp[n-1][2],dp[n-1][0]))<<endl; return 0; }