Comet OJ Contest 8C 符文能量


题目大意:

给定一个长度为$n$的二元组序列$(a_i,b_i)$ 对相邻的$i-1$和$i$合并两个二元组的代价为$b_{i-1}\cdot a_i$ 你还可以选择一个区间 使得这个区间的所有二元组变为$(k\cdot a_i,k\cdot b_i)$ 你也可以不选 求将$n$个区间合并成一个区间的最小代价

题解:

首先假如没有操作的话 合并成一个区间的贡献就是$\sum_{i=2}^{n}b_{i-1}\cdot a[i]$ 不会由于合并顺序的改变而变化 我一开始以为是合并石子ex 也没高兴推

所以我们只要考虑对一段区间加上操作就好了 这就可以进行线性dp

设$f[i][0]$为到第$i$个数还没有进行操作的最小代价

设$f[i][1]$为到第$i$个数正在操作序列中的最小代价

设$f[i][2]$为到第$i$个数已经操作过且第$i$个数不在操作范围里

那么转移方程就可以写成:

$f[i][0]=f[i-1][0]+b_{i-1}\cdot a_i$

$f[i][1]=min(f[i-1][0]+k\cdot b_{i-1}\cdot a_i,f[i-1][1]+k^2\cdot b_{i-1}\cdot a_i)$

$f[i][2]=min(f[i-1][2]+b_{i-1}\cdot a_i,f[i-1][1]+k\cdot b_{i-1}\cdot a_i)$

最后答案即为$min(f[n][0],f[n][1],f[n][2])$

AC代码:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=100050;
const int inf=0x3f3f3f3f;
ll n,k,a[maxn],b[maxn];
ll f[maxn][3];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    for(int i=2;i<=n;i++)
    {
        f[i][0]=f[i-1][0]+b[i-1]*a[i];
        f[i][1]=min(f[i-1][0]+k*b[i-1]*a[i],f[i-1][1]+k*k*b[i-1]*a[i]);
        f[i][2]=min(f[i-1][2]+b[i-1]*a[i],f[i-1][1]+k*b[i-1]*a[i]);
    }
    cout<<min(f[n][0],f[n][2])<<endl;
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
CF1228C Primes and Multiplication CF1228C Primes and Multiplication
这场CF我网炸了 然后赛后补题 这道题应该算是魔改一下阶乘质因数分解 题意翻译直接搬洛谷的了懒得打 1.题意简述: 2.题解:首先我们可以把$x$质因数分解 然后考虑$x$的因子$p$ 对于每一个$p$ 我们都要求出$g(1,p)\cd
2019-10-01
下一篇 
BZOJ1045 糖果传递 BZOJ1045 糖果传递
题意简述:有n个小朋友坐成一圈,每人有$a[i]$个糖果每人只能给左右两人传递糖果,每人每次传递一个糖果代价为1,求使所有人获得均等糖果的最小代价 输入格式:第一行输入一个正整数$n$,表示小朋友的个数 接下来$n$行,每行一个整数$a[
2019-08-25
  目录