题解 CF1207C 【Gas Pipeline】
曦行夜落
2019-08-23 11:20:29
非常优(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;
}
```