yltx's blog

yltx's blog

Κοιτάζοντας πάνω στον έναστρο ουρανό, κάτω στη γη.

题解 CF1207C 【Gas Pipeline】

posted on 2019-08-23 17:19:06 | under 题解 |

这个题就是裸的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$ 。

代码:

#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的高度也是需要柱子的
    }
}