Educational Codeforces 71 C
- 题意：
- 给出你一个字符串，代表油管的形状，但是这个形状不是固定的，你可以改变高为1的管道，管道的价格是a，支柱的价格是b，问你建成这样的管道最少花费多少？
- 题解：
- 贪心策略，题目给出头尾都是高度为1的管柱，每次如果高度为2，要保证左面和右面的柱子一定要为2，如果高度为1，就要讨论是高度为1的花费少还是高度为2的花费少。
- 代码：
#include <bits/stdc++.h> using namespace std; #define ll long long const ll inf = 1e17; char s[200010]; ll ans[200010][2]; int main() { int t; cin>>t; while(t--) { ll n,a,b; cin>>n>>a>>b; scanf("%s",s+1); ans[0][0] = b,ans[0][1] = inf; for(int i=1;i<=n;i++) { if(s[i] == '0'){ ans[i][0] = min(ans[i-1][0],ans[i-1][1]+a)+a+b; ans[i][1] = min(ans[i-1][0]+a+b,ans[i-1][1])+a+2*b; }else{ ans[i][0] = inf; ans[i][1] = min(ans[i-1][0]+a+b,ans[i-1][1])+a+2*b; } } cout<<ans[n][0]<<endl; } return 0; }
CVTE公司福利 258人发布