题目描述

米薇女王万万没有想到考德威尔男爵的真实意图。她的脑海里浮现出莱里亚的秀美山河,可惜再也回不去了。

不过所幸的是,她还有着军队和重整山河的勇气。雷纳德为米薇女王呈上了 nnn 块符文石。符文石可以帮助你更好的战斗。每个符文石拥有能量,米薇可以挑选类型相近的符文石融合并释放出能量。

形象的,我们可以把每个符文石 PiP_iPi 描述成一个二元组 (ai,bi)(a_i,b_i)(ai,bi) 。对于两个相邻的符文石 PiP_iPiPi+1P_{i+1}Pi+1,可以把他们融合为 (ai,bi+1)(a_i,b_{i+1})(ai,bi+1) 并释放出 ai+1∗bia_{i+1}*b_iai+1bi 的能量。融合完的符文石会替换掉原本的两个二元组,出现在他们的位置上。米薇希望把所有的 nnn 个符文石融合成 111 个符文石。你可以以任意顺序合并相邻的两个符文石。

幸运的是,米薇找到了一个法力通天的术士,在全部融合过程前你可以选择一段连续的区间将里面的符文石精炼。即把原本的一段二元组 (ai,bi)(a_i,b_i)(ai,bi)kkk 变为 (ai⋅k,bi⋅k)(a_i \cdot k,b_i \cdot k)(aik,bik)。当然你也可以不选择任何区间。注意此操作必须在初始状态进行。

她希望她释放的能量尽可能小并想知道这个值是多少。

你可以结合样例解释来理解题目。

输入描述

111222 个整数 nnnkkk 。 代表有 nnn 块符文石,精炼符文石的倍率为kkk

接下来 nnn 行,每行 222 个整数 aia_iaibib_ibi 。描述第 iii 个符文石的属性。

  • 2≤n≤1052\leq n\leq 10^52n105
  • 0≤∣ai∣,∣bi∣,∣k∣≤2000 \leq |a_i|,|b_i|,|k|\leq 2000ai,bi,k200

输出描述

一个整数,释放能量的最小值。

样例输入 1

4 -1
-1 -2
2 3
3 4
-3 5

样例输出 1

-25

提示

最优方案下,你可以选择区间 [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=-933=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=-422=4 点能量。

序列变为 (1,4) (−3,5)(1,4)\ (-3,5)(1,4) (3,5)

合并剩余符文石释放出 −12-1212 点能量。序列最终剩下一个符文石 (1,5)(1, 5)(1,5)

释放的能量总和为 (−9)+(−4)+(−12)=−25(-9)+(-4)+(-12)=-25(9)+(4)+(12)=25 点。

观察可以发现,合并的顺序对结果是没有影响的,我们只需要考虑k子段的影响,只有一段区间,线性dp即可
#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;
}