Codeforces #367 Div2 C. Hard problem

Cをしょうもないミスで落としてしまった。
http://codeforces.com/contest/706/problem/C

問題

N個の文字列S[i]と対応するコストC[i]が与えられる。

各S[i]はコストC[i]を払うと文字列を反転させることができる。
これによりSが辞書順に並ぶようにできるか。
出来るならばその最小コストを求めよ。

解法

割と単純なDP。以下の状態を考える。
dp(i,b) := i番目までの文字列を辞書順に並べ、かつi番目を反転させたかどうか(b=0,1)という状態に至る最小コスト
i番目を反転させた場合・させない場合と、(i+1)を反転させた場合・させない場合を比べてdp(i+1,b)を順次更新していく。

int N;
int C[101010];
string S[101010],T[101010];

ll dp[101010][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>C[i];
	FOR(i,N) {
		cin>>S[i];
		T[i]=S[i];
		reverse(ALL(T[i]));
	}
	
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	dp[0][1]=C[0];
	for(i=1;i<N;i++) {
		if(S[i-1]<=S[i]) dp[i][0]=min(dp[i][0],dp[i-1][0]);
		if(S[i-1]<=T[i]) dp[i][1]=min(dp[i][1],dp[i-1][0]+C[i]);
		if(T[i-1]<=S[i]) dp[i][0]=min(dp[i][0],dp[i-1][1]);
		if(T[i-1]<=T[i]) dp[i][1]=min(dp[i][1],dp[i-1][1]+C[i]);
	}
	
	ll mi=min(dp[N-1][0],dp[N-1][1]);
	if(mi>=0x3f3f3f3f3f3f3f3fLL) _P("-1\n");
	else cout<<mi<<endl;
	
	
}

まとめ

仮置きの最大値が十分大きくないというしょうもない理由で落ちた。