题解 CF1207C 【Gas Pipeline】
引领天下
2019-08-23 17:19:06
这个题就是裸的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$。
代码：
```cpp
#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的高度也是需要柱子的
}
}
```