大佬教程收集整理的这篇文章主要介绍了codeforces 1207 C（水dp），大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
You are responsible for installing a gas pipeline along a road. Let‘s consider the road (for simplicity) as a segment [0,@H_618_33@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 @H_696_237@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 @H_761_301@22. Find the shape of the pipeline with minimum possible cost and calculate that cost.
Note that you @H_541_317@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.
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, @H_924_403@@H_515_404@aa, bb (@H_167_419@2≤n≤2⋅1052≤n≤2⋅105, 1@H_489_443@≤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 @R_420_10586@l length of all Strings ss doesn‘t exceed @H_913_607@2⋅1052⋅105.
Print TT Integers — one per query. For each query print the minimum possible cost of the constructed pipeline.
94 25 2900000000 13
主要没想到用dp写，不然随便写写就过了，
利用dp[i][0]表示到第i个路口右边的柱子为普通柱子时所需要的最低花费，dp[i][1]第i个路口右边的柱子为高柱子所需要的最低花费，
如果当前路口是1，那么此时路口右边的柱子只能是高柱子
dp[i][1] = dp[i-1][1] + a + 2*b;
如果当前路口是0，那么右边的柱子可能是普通柱子，也可能是高柱子
如果是普通柱子，
此时左边可能为普通柱子，也可能为高柱子，有：
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);
#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("%lld\n",dp[n][0]); } }
以上是大佬教程为你收集整理的codeforces 1207 C（水dp）全部内容，希望文章能够帮你解决codeforces 1207 C（水dp）所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。