C.Gas Pipeline
10727 ワード
リンク:http://codeforces.com/contest/1207/problem/C
道があります.最初の尾を除いて、途中に交差点があります.いくつかのパイプを設置したいです.交差点がある時は高く上がる必要があります.いろいろなプランで価格が違っています.パイプと柱の費用を与えて、最小の出費を提供します.
欲張りでもいいですが、dpはもっと美的に感じられます.
以下にdpコードを与えます.
道があります.最初の尾を除いて、途中に交差点があります.いくつかのパイプを設置したいです.交差点がある時は高く上がる必要があります.いろいろなプランで価格が違っています.パイプと柱の費用を与えて、最小の出費を提供します.
欲張りでもいいですが、dpはもっと美的に感じられます.
以下にdpコードを与えます.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
#define lowbit(a) ((a)&-(a))
#define speed std::ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
using namespace std;
typedef long long ll;
queue<int> q;
priority_queue<int> pq;
const int maxn = 200005;
ll n,m,l,r;
ll ans=0;
ll dp[maxn][2];
int main()
{
int T;
cin>>T;
while(T--)
{
string s;
ll a,b;
cin>>n>>a>>b;
cin>>s;
dp[0][0]=b;
dp[0][1]=1e15;// , 01 ( )
for(int i=0;i<n;i++)
{
if(s[i]=='0')
{// 0 , 0 ( ) , ( )
dp[i+1][1]=min(dp[i][0]+a*2+2*b,dp[i][1]+a+b*2);// 1 , ,
dp[i+1][0]=min(dp[i][0]+a+b,dp[i][1]+a*2+b);// 0 , ,
}
else{
dp[i+1][1]=dp[i][1]+a+2*b,dp[i+1][0]=1e15;//+a+2*b
}// 1, 0 ( 0 ), ,
}
printf("%I64d
",dp[n][0]);// ,n ,0 ( )
}
return 0;
}