TopCoder SRM 348 Div1 Easy LostParentheses

問題

数字および+,-からなる式が与えられる。
この式に括弧を適切に挿入し、式の値が最も小さくなるようにしたい。

式の値の最小値はいくつか、求めよ。

制約条件

式は50文字以下
出てくる数字は5桁以下

方針

動的計画法による。
i番目からj番目の項に適当に括弧を挿入したときにできる値の最大値をmn[i][j]
最大値をmx[i][j]として、これを更新していくようなDPをすればよい。

ソースコード

int n,num[50],sig[50];
int mn[60][60],mx[60][60];

class LostParentheses {
	public:
	int minResult(string e) 
	{
		n=1;
		rep(i,e.size())if(e[i]=='+'||e[i]=='-'){
			sig[n++]=e[i]=='+'?1:-1;
			e[i]=' ';
		}
		stringstream ss(e);
		n=0;
		while(ss>>num[n])n++;
		rep(i,n)rep(j,n){
			mn[i][j]=i!=j?inf:num[i];
			mx[i][j]=i!=j?-inf:num[i];
		}
		for(int l=2;l<=n;l++)rep(i,n-l+1){
			for(int m=i;m<i+l-1;m++){
				int a=mn[i][m]+mn[m+1][i+l-1]*sig[m+1], b=mn[i][m]+mx[m+1][i+l-1]*sig[m+1];
				int c=mx[i][m]+mn[m+1][i+l-1]*sig[m+1], d=mx[i][m]+mx[m+1][i+l-1]*sig[m+1];
				mn[i][i+l-1]=min(mn[i][i+l-1],min(min(a,b),min(c,d)));
				mx[i][i+l-1]=max(mx[i][i+l-1],max(max(a,b),max(c,d)));
			}
		}
		return mn[0][n-1];
	}
};