Facebook hacker cup qualification B. Balanced Smileys

2013-01-31

22:35 |

[a-z: ()] からなる文字列が与えられる。":)" と ":(" はそれ単体で１文字ともみなせる。カッコの対応が合う解釈があるかどうかを YES NO で答える問題。
|文字列|≦100

スタックとか使うのか？いやなんかいろいろ反例があって failed system test になりそうなので大変きな臭い。大変きな臭い。
手堅く区間DPでやろう
問題文から以下の定義になる

BalancedParentheses ::=
	  Empty
	| [a-z: ]
	| :)
	| :(
	| ( BalancedParentheses )
	| BalancedParentheses BalancedParentheses

ので、始点 S 終点 E で表される長さ L の部分文字列 s が与えられた時、それが BalancedParenthesis かどうかを定義通りに求める。
これをすべての S, E に対して行う。ただし L が小さい順にやる。

Accepted

int main() {
	int T;
	cin>>T;
	cin.ignore();
	REP(ttt, T) {
		string s;
		getline(cin, s);
		
		int N=s.size();
		VVI dp(N, VI(N+1));
		REP(S, N) dp[S][0]=1;
		
		RANGE(L, 1, N+1) {
			REP(S, N) {
				int E=S+L-1;
				if(E>=N) continue;
				
//				cout<<s.substr(S, L)<<endl;
				
//				cout<<S<<" "<<L<<endl;
				if(L==0) dp[S][L]=1;
				if(L==1 && (s[S]==' ' || s[S]==':' || ('a'<=s[S] && s[S]<='z'))) dp[S][L]=1;
				if(L==2 && (s.substr(S, L)==":)" || s.substr(S, L)==":(")) dp[S][L]=1;
				if(L-2>=0 && s[S]=='(' && dp[S+1][L-2] && s[E]==')') dp[S][L]=1;
				if(L-2>=0) {
					RANGE(l, 1, L) if(dp[S][l] && dp[S+l][L-l]) dp[S][L]=1;
//					RANGE(l, 1, L) assert(0<=S && S<N && S+l<N && 0<L-l && L-l<=N);
				}
			}
		}
		
		cout<<"Case #"<<ttt+1<<": "<<(dp[0][N]?"YES":"NO")<<endl;
//		break;
	}
	return 0;
}