C. Gas Pipeline（1207C）

2024-04-16 02:58

文章标签 pipeline gas 1207c

本文主要是介绍C. Gas Pipeline（1207C），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

C. Gas Pipeline
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are responsible for installing a gas pipeline along a road. Let’s consider the road (for simplicity) as a segment [0,?] on ?? axis. The road can have several crossroads, but for simplicity, we’ll denote each crossroad as an interval (?,?+1) with integer ?. So we can represent the road as a binary string consisting of ? characters, where character 0 means that current interval doesn’t contain a crossroad, and 1 means that there is a crossroad.

Usually, we can install the pipeline along the road on height of 1 unit with supporting pillars in each integer point (so, if we are responsible for [0,?] road, we must install ?+1 pillars). But on crossroads we should lift the pipeline up to the height 2, so the pipeline won’t obstruct the way for cars.

We can do so inserting several zig-zag-like lines. Each zig-zag can be represented as a segment [?,?+1] with integer ? consisting of three parts: 0.5 units of horizontal pipe + 1 unit of vertical pipe + 0.5 of horizontal. Note that if pipeline is currently on height 2, the pillars that support it should also have length equal to 2 units.

Each unit of gas pipeline costs us ? bourles, and each unit of pillar — ? bourles. So, it’s not always optimal to make the whole pipeline on the height 2. Find the shape of the pipeline with minimum possible cost and calculate that cost.

Note that you must start and finish the pipeline on height 1 and, also, it’s guaranteed that the first and last characters of the input string are equal to 0.

Input
The fist line contains one integer ? (1≤?≤100) — the number of queries. Next 2⋅? lines contain independent queries — one query per two lines.

The first line contains three integers ?, ?, ? (2≤?≤2⋅105, 1≤?≤108, 1≤?≤108) — the length of the road, the cost of one unit of the pipeline and the cost of one unit of the pillar, respectively.

The second line contains binary string ? (|?|=?, ??∈{0,1}, ?1=??=0) — the description of the road.

It’s guaranteed that the total length of all strings ? doesn’t exceed 2⋅105.

Output
Print ? integers — one per query. For each query print the minimum possible cost of the constructed pipeline.

Example
inputCopy
4
8 2 5
00110010
8 1 1
00110010
9 100000000 100000000
010101010
2 5 1
00
outputCopy
94
25
2900000000
13
Note
The optimal pipeline for the first query is shown at the picture above.

The optimal pipeline for the second query is pictured below:

The optimal (and the only possible) pipeline for the third query is shown below:

The optimal pipeline for the fourth query is shown below:

题意： 二进制01串。为1代表这个地方得是高度为2的柱子，为0代表可以为高度为1或者2的柱子。起点和终点柱子高度都为1。同时横向走的时候需要管道。柱子的单位花费是b，管道的单位花费是a。问怎么安排使得花费最小

思路： 这种模拟题细节很多，关键就在于：思路一定要清晰。机房几个大佬卡在这里，都是因为一些小细节：循环边界问题，long long问题，变量毒瘤问题。

n个点的话，会有n+1个柱子，有柱子的地方就标上号。二进制为1的话，1这个格子代表的两个点都得是高柱子。高柱子中间的部分，就是贪心的地方。

首先确定基础花费：n个管道：na，n+1个低柱子：nb，2个转折管道：2a（全是0的话没有）。中间可以高柱子的部分，假设长度为x，选择高柱子，额外花费为xb。选择低柱子，花费为2*a。选择最小的就可以了。

注意：起点终点一定是低柱子！！

#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cstring>using namespace std;
typedef long long ll;
const ll maxn = 2e5 + 7;
#define INF 0x3f3f3f3fll maze[maxn];
char str[maxn];
int main()
{ll T;scanf("%lld",&T);while(T--){memset(maze,0,sizeof(maze));ll n,a,b;scanf("%lld%lld%lld",&n,&a,&b);scanf("%s",str);ll sta = INF,en = 0;for(ll i = 0;i < n;i++){if(str[i] == '1'){maze[i] = 1;maze[i+1] = 1;sta = min(sta,i);en = max(en,i + 1);}}ll num0 = 0,num1 = 0;ll ans = 0;for(ll i = sta;i <= en;i++){if(maze[i] == 0)num0++;else{num1++;ll tmp = 0;tmp = min(num0 * b,2 * a);ans += tmp;num0 = 0;}}ans += 2 * a + n * a + (n + 1) * b + num1 * b;if(sta == INF && en == 0)ans -= 2 * a;printf("%lld\n",ans);}return 0;
}