如何用动态规划解决Codeforces 1207 C题中的长尾词问题？

本文共计1454个文字，预计阅读时间需要6分钟。

C.+输气管道+测试时间限制+每测试2秒+内存限制+每测试256兆字节+输入+标准输入+输出+标准输出+您负责沿道路安装输气管道。让我们考虑道路（为了简单起见）为一个简单的一维线段+

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][0,n]onOX">OXOXaxis. The road can have several crossroads, but for simplicity, we‘ll denote each crossroad as an interval(x,x+1)">(x,x+1)(x,x+1)with integerx">xx. So we can represent the road as a binary string consisting ofn">nncharacters, where character0means that current interval doesn‘t contain a crossroad, and1means that there is a crossroad.

Usually, we can install the pipeline along the road on height of1">11unit with supporting pillars in each integer point (so, if we are responsible for[0,n]">[0,n][0,n]road, we must installn+1">n+1n+1pillars). But on crossroads we should lift the pipeline up to the height2">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][x,x+1]with integerx">xxconsisting of three parts:0.5">0.50.5units of horizontal pipe +1">11unit of vertical pipe +0.5">0.50.5of horizontal. Note that if pipeline is currently on height2">22, the pillars that support it should also have length equal to2">22units.

Each unit of gas pipeline costs usa">aabourles, and each unit of pillar —b">bbbourles. So, it‘s not always optimal to make the whole pipeline on the height2">22. Find the shape of the pipeline with minimum possible cost and calculate that cost.

Note that youmuststart and finish the pipeline on height1">11and, also, it‘s guaranteed that the first and last characters of the input string are equal to0.

Input

The fist line contains one integerT">TT(1≤T≤100">1≤T≤1001≤T≤100) — the number of queries. Next2⋅T">2⋅T2⋅Tlines contain independent queries — one query per two lines.

The first line contains three integersn">nn,a">aa,b">bb(2≤n≤2⋅105">2≤n≤2⋅1052≤n≤2⋅105,1≤a≤108">1≤a≤1081≤a≤108,1≤b≤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 strings">ss(|s|=n">|s|=n|s|=n,si∈{0,1}">si∈{0,1}si∈{0,1},s1=sn=0">s1=sn=0s1=sn=0) — the description of the road.

It‘s guaranteed that the total length of all stringss">ssdoesn‘t exceed2⋅105">2⋅1052⋅105.

Output

PrintT">TTintegers — 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写，不然随便写写就过了，

利用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]); } }