CF1207C Gas Pipeline


题目大意:

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

题解:

现场想到模拟贪心 但是写起来太麻烦了 其实对于每个柱子 都可以选择时高度为二还是高度为一($s[i]=s[i-1]=0$时该柱子才可以是高度为1) 对于每个决策只有两个转移 因此可以考虑dp 令$f[i][0/1]$表示考虑到第$i$个柱子高度是1/2时的最小花费 转移方程即为:

$f[i][0]=min(f[i-1][0]+a+b,f[i-1][1]+2a+b)(s[i]=s[i-1]=0)$

$f[i][1]=min(f[i-1][1]+a+2b,f[i-1][0]+2a+2b)$

最后答案即为$f[n][0]$

注意由于我们是用$s[i]$和$s[i-1]$来判断能不能高度为1的 所以还需要使得$s[n]=0$

AC代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const int maxn=200050;
const ll inf=1e15;
ll f[maxn][2];
ll T,n,a,b;
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>a>>b;
        string s;cin>>s;
        s[n]='0';
        for(int i=0;i<=n;i++) f[i][0]=f[i][1]=inf;
        f[0][0]=b;
        for(int i=1;i<=n;i++)
        {
            f[i][1]=min(f[i-1][0]+2*a+2*b,f[i-1][1]+a+2*b);
            f[i][0]=min(f[i-1][0]+a+b,f[i-1][1]+2*a+b);
            if(s[i]=='1'||s[i-1]=='1') f[i][0]=inf;
        }
        cout<<f[n][0]<<endl;
    }
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
BZOJ1257 余数之和 BZOJ1257 余数之和
题目大意:给出正整数$n$和$k$ 计算$j(n, k)=k \mod 1 + k \mod 2 + k \mod 3 + … + k \mod n$的值 题解:首先$k\mod n=k-\lfloor{\frac{k}{n}}\rflo
2019-08-25
下一篇 
hdu6681 Rikka with Cake hdu6681 Rikka with Cake
题目大意:给出$k$条射线 求能使$n*m$的矩形分成多少个块 题解:由于是射线 所以所以每个一个交点都能产生贡献 最后的答案就是总交点数+1 那如何去维护呢 我们可以把$k$条射线按横纵来考虑 对于竖的射线 假如为$U$ 那么$[y,m]
2019-08-24
  目录