PKU 1404 I-Keyboard

• 動的計画法
• 縦に何番目のキー、横に何番目の文字を取る
• 更新の条件式を工夫することで最後のキーに多く割り当てることが出来る
• ただし以下の解答は本当に条件を満たすかどうか未確認

static int dp[128][128];
static int previous[128][128];

int main() {
	int T;
	cin >> T;
	for (int t = 1; t <= T; ++t) {
		int K, L;
		cin >> K >> L;
		string dummy, key, alphabet;
		getline(cin, dummy);
		getline(cin, key);
		getline(cin, alphabet);

		//assert(K == key.size());
		//assert(L == alphabet.size());

		vector<int> F;
		for (int i = 0; i < L; ++i) {
			int f;
			cin >> f;
			F.push_back(f);
		}

		fill_n((int*)dp, sizeof(dp) / sizeof(dp[0][0]), INT_MAX);
		fill_n((int*)previous, sizeof(previous) / sizeof(previous[0][0]), INT_MAX);

		dp[0][0] = 0;
		for (int k = 0; k < K; ++k) {
			for (int begin = 0; begin < L; ++begin) {
				if (dp[k][begin] == INT_MAX) {
					continue;
				}

				int cost = dp[k][begin];
				for (int end = begin + 1; end <= L; ++end) {
					cost += (end - begin) * F[end - 1];

					if (dp[k + 1][end] > cost) {
						dp[k + 1][end] = cost;
						previous[k + 1][end] = begin;
					}
				}
			}
		}

		vector<int> path;
		int currentEnd = L;
		for (int currentK = K; currentK >= 0; --currentK) {
			path.push_back(currentEnd);
			currentEnd = previous[currentK][currentEnd];
		}
		reverse(path.begin(), path.end());

		printf("Keypad #%d:\n", t);
		for (int k = 0; k < K; ++k) {
			printf("%c: %s\n", key[k], alphabet.substr(path[k], path[k + 1] - path[k]).c_str());
		}
		printf("\n");
	}
}