TopCoder SRM 578 Div2 Hard WolfInZooDivTwo

Div1 MediumとDiv2 Hardは似ているけどDiv2 Hardの方が若干簡単なのでこちらから。
http://community.topcoder.com/stat?c=problem_statement&pm=12533

問題

N個のマス目があり、各マスには狼が１匹いる場合がある。
ここで[L,R]の２値からなる集合が与えられる。
各[L,R]の範囲には、１匹以上の狼がいるとする。

このとき、Nマスの狼の配置の組み合わせ数を答える。

解法

まず、[L,R]の集合を処理し、各マスXに対して、そこから最低１匹狼がいないといけない右限A[X]を求める。
あとは、各マスPに対し(N-1)から0まで順にDPしていく。
その際以下の２条件で組み合わせを計算する。

• Pの右で最寄の狼がいるマスQに対し、A[P]
• そうでない場合は、Pに狼を配置してもしなくても良い。

全体でO(N^2)で済む。

ll mo=1000000007;

class WolfInZooDivTwo {
	public:
	int MR[301];
	
	string concatvec(vector <string> expr) {
		int i;
		string st="";
		FOR(i,expr.size()) st += expr[i];
		return st;
	}
	vector<int> split_int(const string &str, char delim){
		vector<int> res;
		size_t current = 0, found;
		while((found = str.find_first_of(delim, current)) != string::npos){
			string s = string(str, current, found - current);
			res.push_back(atoi(s.c_str()));
			current = found + 1;
		}
		string s = string(str, current, str.size() - current);
		res.push_back(atoi(s.c_str()));
		return res;
	}
	
	int count(int N, vector <string> L, vector <string> R) {
		int i,x,y;
		int inval[301];
		vector<int> LI=split_int(concatvec(L),' ');
		vector<int> RI=split_int(concatvec(R),' ');
		
		FOR(x,N) MR[x]=-1;
		FOR(x,LI.size()) {
			if(MR[LI[x]]==-1) MR[LI[x]]=RI[x];
			else MR[LI[x]]=min(MR[LI[x]],RI[x]);
		}
		
		ll DP[301][301];
		ZERO(DP);
		DP[N][N]=1;
		for(x=N-1;x>=0;x--) {
			for(y=x+1;y<=N;y++) {
				DP[x][x]=(DP[x][x] + DP[x+1][y])%mo;
				if(MR[x]==-1 || MR[x]>=y) DP[x][y]=DP[x+1][y];
			}
		}
		
		ll res=0;
		FOR(x,N+1) res=(res+DP[0][x])%mo;
		return (int)res;
	
	}
};

まとめ

文字列連結・整数化に妙に長いコードを使ってるのが嫌だ。
もっと簡単にならんかな。stringstreamとか使うとよい？