首页 > 其他分享 > 海底高铁(洛谷3406)

海底高铁(洛谷3406)

时间:2023-05-28 16:47:33浏览次数:42  
标签:洛谷 int 高铁 long ans 3406

 

 

 

 

 

#include <iostream>

using namespace std;

const int N = 100010;
int p[N];//要去的城市
int A[N], B[N], C[N];
long long s, ans[N];//ans差分数组
int main()
{
    int N, M;
    scanf("%d%d", &N, &M);
    for(int i = 1; i <= M; i ++ )//要去的城市
    {
        scanf("%d", &p[i]);
    }
    // 输入每段路的Ai Bi Ci 有N - 1段路
    for(int i = 1; i <= N - 1; i ++ ) scanf("%d%d%d", &A[i], &B[i], &C[i]);
    
    for(int i = 1; i <= M - 1; i ++ )//要去M个城市,相邻城市间有一小段路,因此经过M - 1
    {    //用差分保存经过的次数
        ans[min(p[i], p[i + 1])] ++;//让前面的++ 后面的--
        ans[max(p[i], p[i + 1])] --;
    }
    
    //求他的前缀和然后再全部赋值给他这个差分数组 此时该数组存的就是经过次数
    for(int i = 1; i <= N; i ++ ) ans[i] += ans[i - 1];
    
    //N-1段路 看看哪个方案比较省钱 算一下最min花钱的并存入s
    for(int i = 1;  i <= N - 1; i ++ ) s += min(A[i] * ans[i], (B[i] * ans[i] + C[i]));
    printf("%lld", s);
    return 0;
    
}

 

标签:洛谷,int,高铁,long,ans,3406
From: https://www.cnblogs.com/FISH-Q/p/17438446.html

相关文章

  • 洛谷3397地毯
        问题分析:这个比y总的二维差分模板要简单一些,因为他一开始的矩阵都为0,而且矩阵是一个n方阵,那么其实可以用y总的模板来写,下面是二维差分矩阵的原理  #include<iostream>usingnamespacestd;constintN=1010;intb[N][N];voidinsert(intx1,in......
  • 洛谷 P9344. 去年天气旧亭台
    去年天气旧亭台题目背景依旧是过往的天气,过往的楼台烟雨。时间悄悄流逝着,山河仍在,人却已不是过去的人……题目描述登上楼台,旧时满面沉灰的地板映入眼帘。共有$n$块地板,地板分为两类,第$i$块地板的类别用$c_i$表示,积灰程度用$a_i$表示。注意$c_i$为$0$或$1$。现......
  • 洛谷 P9248 - [集训队互测 2018] 完美的集合
    显然,如果选择的\(k\)个“合法集合”固定了,那么可以放置装置的点如果存在,那么必然形成一个连通块,也就是说,答案等于所有合法方案中,可以放置装置的点形成的连通块个数之和。而根据点减边的套路,这等价于,枚举每个点,计算有多少种方案满足可以在其放置装置,再枚举每条边,计算有多少种方案......
  • 洛谷颜色对照表
    $$\def\arraystretch{1.2}\begin{array}{|c|l|l||c|l|l|}\hline颜色名称&十六进制编码&\text{RGB对应值}&颜色名称&十六进制编码&\text{RGB对应值}\\\hline\color{#52C41A}\text{AC绿}&\text{52C41A}&\text{(82,196,26)}&\color{#FE4C......
  • 洛谷 P8978 「DTOI-4」中位数
    首先考虑二分答案,把原序列变成01序列。那么问题就相当于转换成判断能否在\(k\)次操作内,将序列变成全\(1\)。由于每次操作一定可以做到把\(1\)的个数\(n\)变成\(n'=2n-1\)。因此可以得知操作一定是\(\logn\)级别的。但是这个问题仍然不太好做,很多贪心都是假的。考虑最......
  • 洛谷 P7999 [WFOI - 01] 翻转序列(requese)
    洛谷传送门注意到如果\(n\)足够小,可以过\(n^2\)。选\(x=3\)(这样做的好处是能交换两个相邻元素),每次把值为\(i\)的元素挪到\(i\),注意到我们不关心其他元素,所以翻转\([l,r]\)的效果可以看成是交换\(p_l,p_r\)。于是先跳大步,再跳小步。可以过\(n\le100\),拿到50分......
  • 洛谷 P4544 [USACO10NOV]Buying Feed G - 题解
    https://www.luogu.com.cn/problem/P4544感觉是很没意思的DP+DS优化,以前做过几道更难的题:https://codeforces.com/contest/1788/problem/Ehttps://atcoder.jp/contests/abc288/tasks/abc288_f这种题只要是让我写总是能把代码整的伤痕累累(逃第一眼:我艹不就是一个sbDP吗......
  • 机器分配 P2066 洛谷
    #dp#背包求方案#分组背包#字典序#T3机器分配P2066机器分配-洛谷|计算机科学教育新生态(luogu.com.cn)题目描述总公司拥有高效设备M台,准备分给下属的N个分公司。各分公司若获得这些设备,可以为国家提供一定的盈利。问:如何分配这M台设备才能使国家得到的盈利最大?求出......
  • 洛谷 P5488 差分与前缀和
    洛谷传送门看起来很毒瘤,但是推出贡献系数后就是一个朴素的卷积了。首先考虑前缀和。考虑\(j\(j\lei)\)的\(a_j\)贡献到\(i\)的过程,是找到\(j=p_0\lep_1\le\cdots\lep_k=i\)的方案数。令\(x_i=p_i-p_{i-1}\),即求\(x_i\ge0,\sum\limits_{i=1}^kx_i......
  • 洛谷 P3321 [SDOI2015] 序列统计
    洛谷传送门感觉挺综合的一道题。考虑朴素dp,\(\forallx\inS,f_{i+1,jx\bmodm}\getsf_{i,j}\)。复杂度\(O(nm^2)\)。显然可以矩乘优化至\(O(m^3\logn)\),但是不能通过。如果转移式中是加法而不是乘法,那很容易卷积优化。接下来是一个很重要的套路:化乘为加。实数......