C.Gas Pipeline

10727 ワード

リンク:http://codeforces.com/contest/1207/problem/C
道があります.最初の尾を除いて、途中に交差点があります.いくつかのパイプを設置したいです.交差点がある時は高く上がる必要があります.いろいろなプランで価格が違っています.パイプと柱の費用を与えて、最小の出費を提供します.
欲張りでもいいですが、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; }