Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-04SRM349 (Practice)

SRM 348 LostParentheses

|  SRM 348 LostParentheses - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 348 LostParentheses - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7754

  • Greedyなアルゴリズムなんて思いつかないので、区間DPをする
import java.util.Arrays;

public class LostParentheses {
	int INF = 1000000;
	int[] nums, ops;
	int[][] memo;
	
	public int dfs(int from, int to) {
		if (from == to) {
			return nums[from];
		}
		if (memo[from][to] != INF) {
			return memo[from][to];
		}
		
		int ret = INF;
		for (int j = from ; j < to ; j++) {
			int a = dfs(from, j);
			int b = dfs(j+1, to);
			if (ops[j+1] == 1) {
				ret = Math.min(ret, a + b);
			} else if (ops[j+1] == -1) {
				ret = Math.min(ret, a - b);
			}
		}
		memo[from][to] = ret;
		return ret;
	}
	
	
	public int minResult(String e) {
		String[] numstrs = e.split("[+-]");
		nums = new int[numstrs.length];
		for (int i = 0 ; i < numstrs.length ; i++) {
			nums[i] = Integer.valueOf(numstrs[i]);
		}
		
		String[] opstrs = e.split("[0-9]+");
		ops = new int[opstrs.length];
		for (int i = 0 ; i < opstrs.length ; i++) {
			if ("+".equals(opstrs[i])) {
				ops[i] = 1;
			} else if ("-".equals(opstrs[i])) {
				ops[i] = -1;
			}
		}
		
		memo = new int[nums.length+1][nums.length+1];
		for (int i = 0 ; i < nums.length+1 ; i++) {
			Arrays.fill(memo[i], INF);
		}
		
		return dfs(0, nums.length-1);
	}
}