Fork me on GitHub

题解 CF1207C 【Gas Pipeline】

这个题就是裸的dp,然而我还是莫名其妙手残打错了一次。

思路:对于每个位置,我们令$f[i][0]$为到达$i$时高度为$1$的最小答案,$f[i][1]$为到达$i$时高度为$2$的最小答案,分情况讨论之后dp:

  • 是路口

    • 那么$i$位置高度不能为$0$,反映在dp上就是$f[i][0]=inf$
    • 我们对$f[i][1]$取$min$:看是从上一个位置下来再上来便宜,还是直接拉过来便宜。
  • 不是路口

    • 那么$f[i][0]$就是对从上一个位置下来和直接平的过来取$min$
    • $f[i][1]$同是路口的情况,也是分上来和直接平行过来取$min$。

代码:

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
#include<bits/stdc++.h>
using namespace std;
int t,n,k;
string s;
#define ll long long
#define inf 884888488848997
//注意!inf要开大!不然会WA的QAQ
ll a,b,f[200005][2];
int main(){
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
cin>>t;
while(t--){
cin>>n>>a>>b>>s;
memset(f,0,sizeof(f));
f[0][1]=inf;f[0][0]=a+b;
for (int i=1;i<s.size();i++){
k=(s[i]=='1');
if(k){//是路口
f[i][0]=inf;
f[i][1]=min(f[i-1][0]+2*a+2*b,f[i-1][1]+2*b+a);//从f[i-1][0]和f[i-1][1]转移
}else{
f[i][0]=min(f[i-1][0]+a+b,f[i-1][1]+2*a+2*b);
f[i][1]=min(f[i-1][0]+2*a+b,f[i-1][1]+2*b+a);//同上,思路已经说过了
}
}
cout<<f[n-1][0]+b<<endl;//输出答案的时候要注意,最后要求高度降为1,而且1的高度也是需要柱子的
}
}