codeforces 1207 C（水dp）
|
C. Gas Pipeline
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are responsible for installing a gas pipeline along a road. Let‘s consider the road (for simplicity) as a segment?[0,n][0,n]?on?OXOX?axis. The road can have several crossroads,but for simplicity,we‘ll denote each crossroad as an interval?(x,x+1)(x,x+1)?with integer?xx. So we can represent the road as a binary string consisting of?nn?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?11?unit with supporting pillars in each integer point (so,if we are responsible for?[0,n][0,n]?road,we must install?n+1n+1?pillars). But on crossroads we should lift the pipeline up to the height?22,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?[x,x+1][x,x+1]?with integer?xx?consisting of three parts:?0.50.5?units of horizontal pipe +?11?unit of vertical pipe +?0.50.5?of horizontal. Note that if pipeline is currently on height?22,the pillars that support it should also have length equal to?22?units.
Each unit of gas pipeline costs us?aa?bourles,and each unit of pillar —?bb?bourles. So,it‘s not always optimal to make the whole pipeline on the height?22. 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?11?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?TT?(1≤T≤1001≤T≤100) — the number of queries. Next?2?T2?T?lines contain independent queries — one query per two lines. The first line contains three integers?nn,?aa,?bb?(2≤n≤2?1052≤n≤2?105,?1≤a≤1081≤a≤108,?1≤b≤1081≤b≤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?ss?(|s|=n|s|=n,?si∈{0,1}si∈{0,1},?s1=sn=0s1=sn=0) — the description of the road. It‘s guaranteed that the total length of all strings?ss?doesn‘t exceed?2?1052?105.
Output
Print?TT?integers — one per query. For each query print the minimum possible cost of the constructed pipeline.
Example
input
Copy
4 8 2 5 00110010 8 1 1 00110010 9 100000000 100000000 010101010 2 5 1 00
output
Copy
94 25 2900000000 13 利用dp[i][0]表示到第i个路口右边的柱子为普通柱子时所需要的最低花费，dp[i][1]第i个路口右边的柱子为高柱子所需要的最低花费， 如果当前路口是1，那么此时路口右边的柱子只能是高柱子 如果当前路口是0，那么右边的柱子可能是普通柱子，也可能是高柱子 如果是高柱子， #include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <string> #include <map> #include <iomanip> #include <algorithm> #include <queue> #include <stack> #include <set> #include <vector> //const int maxn = 1e5+5; #define ll long long ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} #define MAX INT_MAX #define FOR(i,a,b) for( int i = a;i <= b;++i) #define bug cout<<"--------------"<<endl using namespace std; ll inf = 0x3f3f3f3f3f3f3f3f; char s[210000]; int a,b,n,T; ll dp[210000][5]; int main() { cin>>T; while(T--) { scanf("%d%d%d",&n,&a,&b); scanf("%s",s+1); FOR(i,1,n) dp[i][1] = dp[i][0] = inf; dp[0][1] = inf; dp[0][0] = b; for(int i =1;i<=n;++i) { if(s[i] == ‘1‘) { dp[i][1] = dp[i-1][1] + a + 2*b; } else { dp[i][0] = min(dp[i-1][0] + a + b,dp[i-1][1] + 2*a + b); dp[i][1] = min(dp[i-1][0] + 2*a + 2*b,dp[i-1][1] + a + 2*b); } } printf("%lldn",dp[n][0]); } } （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
