题解 CF1207C 【Gas Pipeline】

发表于 更新于 阅读次数： Waline：
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的高度也是需要柱子的
    }
}