Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-24SRM340, SRM341, SRM342 (Practice)

SRM 342 ReverseResources

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

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

  • 動的計画法
    • 典型っぽいのでこのぐらいはサクッと解けるようになりたい
import java.util.Arrays;

public class ReverseResources {
	long MOD = 1000000007;
	
	String match;
	String[] parts;
	int len;
	
	long[][] dp;
	long[][][][] dp2;

	public long dfs(int from, int to, int i, int j) {
		long ptn = 0;
		if (from > to) {
			return 0;
		}
		if (dp2[from][to][i][j] >= 0) {
			return dp2[from][to][i][j];
		}

		boolean lf = (j == parts[i].length());
		boolean gf = (from == to);
		if (lf || gf) {
			if (lf && gf) {
				ptn = 1;
			} else {
				ptn = 0;
			}
			dp2[from][to][i][j] = ptn;
			return ptn;
		}
		
		if (parts[i].charAt(j) == '%') {
			for (int rep = from + 1 ; rep <= to ; rep++) {
				long after = dfs(rep, to, i, j+2) % MOD;
				if (after >= 1) {
					long a = ((dfs(from, rep) % MOD) * after) % MOD;
					ptn = (ptn + a) % MOD;
				}
			}
		} else if (parts[i].charAt(j) == match.charAt(from)){
			ptn = dfs(from+1, to, i, j+1);
		} else {
			ptn = 0;
		}
		
		dp2[from][to][i][j] = ptn;
		return ptn;
	}

	
	public long dfs(int from, int to) {
		if (from >= to) {
			return 1;
		}
		if (dp[from][to] >= 0) {
			return dp[from][to];
		}
		
		long ret = 0;
		for (int i = 0 ; i < len ; i++) {
			ret += dfs(from, to, i, 0);
			ret %= MOD;
		}
		dp[from][to] = ret;
		return ret;
	}
	
	
	public int findDecompositions(String str, String[] resources) {
		dp = new long[101][101];
		dp2 = new long[31][31][51][51];
		for (int i = 0 ; i < 101 ; i++) {
			Arrays.fill(dp[i], -1);
		}
		for (int i = 0 ; i < 31 ; i++) {
			for (int j = 0 ; j < 31 ; j++) {
				for (int k = 0 ; k < 51 ; k++) {
					Arrays.fill(dp2[i][j][k], -1);
				}
			}
		}
		
		match = str;
		parts = resources;
		len = resources.length;
		return (int)dfs(0, str.length());
	}
}