1042.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1042 on 2005-12-09 at 17:11:01 */ 
#include <cstdio>
#include <cstring>

const int MAX = 128;
const int INF = 100000000;

int main()
{
	int t, T, i, j, k;
	int n, m;
	char board[MAX], letter[MAX];
	int fre[MAX], cost[MAX][MAX];
	int min[MAX][MAX], prev[MAX][MAX], next[MAX];

	scanf("%d", &T);
	for(t = 1; t <= T; t++) {
		scanf("%d %d\n", &n, &m);
		gets(board);
		gets(letter);
		for(i = 0; i < m; i++) {
			scanf("%d", &fre[i]);
		}
		for(i = 0; i < m; i++) {
			cost[i][i] = fre[i];
			for(j = i+1; j < m; j++) {
				cost[i][j] = cost[i][j-1] + (j-i+1) * fre[j];
			}
		}
		int l = m < n ? m : n;
		for(i = 0; i < m; i++) {
			min[i][1] = cost[0][i];
			prev[i+1][1] = 0;
			for(j = 2; j <= n && j <= i+1; j++) {
				min[i][j] = INF;
				for(k = j-2; k < i; k++) {
					if(min[i][j] > min[k][j-1] + cost[k+1][i]) {
						min[i][j] = min[k][j-1] + cost[k+1][i];
						prev[i+1][j] = k + 1;
					}
				}
			}
		}
		for(i = m, j = l; i != 0; i = prev[i][j], j--) {
			next[prev[i][j]] = i;
		}
		printf("Keypad #%d:\n", t);
		for(i = 0, k = 0; i != m; i = next[i], k++) {
			printf("%c: ", board[k]);
			for(j = i; j < next[i]; j++) {
				putchar(letter[j]);
			}
			putchar('\n');
		}
		putchar('\n');
	}
	
	return 0;
}