题解 CF1207C 【Gas Pipeline】

非常优(jian)秀(dan)典(du)型(liu)的一道DP题目 首先我们看到这道题的贪心是显然会被卡掉的（~~我都没想~~） 这道题的Dp明显之处就在于他是一个线性的，而且**后面的选择与前面无关**的题，发现了这点就发现了Dp 然后，对于这样的每个点出两种选择的题目，只需要把两种选择都作为状态存在Dp数组里面 比如本题，我们用$dp[i][1]$和$dp[i][2]$表示该点在高度为$1$和$2$的状态下最小的代价（**第一步，确定状态**） 那么显然可以得到转移方程（**第二步，写出方程**） $dp[i][1]=min(dp[i-1][1]+a+b,dp[i-1][2]+2a+b)$ $dp[i][2]=min(dp[i-1][1]+2a+2b,dp[i-1][2]+a+2b)$ 下面对照着讲一下 第一条，这里修高度为$1$的柱子，如果上一个修的也是$1$，平着过来代价为$a$，修一个高为$1$的柱子代价为$b$。 其他的此处不多叙说，留给读者思考 然后**第三步，确定边界**，显然这里要从$0$点开始，那么$dp[0][1]=b$，题目里说要从高度$1$开始从高度$1$结束，所以答案就是$dp[n][1]$ 同时在Dp过程中，要注意十字路口高度必须为$2$，此时直接把$1$跳过即可，具体见代码（还是比较简单的一道DpQwQ） ------------ ```cpp #include<bits/stdc++.h> #define maxn (200000+500) #define ll long long using namespace std; char s[maxn]; ll a,b,n; ll f[maxn][3]; int main() { int T; scanf("%d",&T); while (T--) { scanf("%I64d%I64d%I64d",&n,&a,&b); scanf("%s",s+1); memset(f,0x3f,sizeof(f)); //最小化，设无穷大 f[0][1]=b; //初始化 for (int i=1;i<=n;++i) { f[i][2]=min(f[i-1][1]+2*a+2*b,f[i-1][2]+a+2*b); //方程2 if (s[i]==49 || s[i+1]==49) continue; //如果有路口不考虑1 f[i][1]=min(f[i-1][2]+2*a+b,f[i-1][1]+a+b); //方程1 } printf("%I64d\n",f[n][1]); //输出答案 } return 0; } ```