给定一个二进制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$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#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;
}
|