http://poj.org/problem?id=1404
题意 ：手机上的要发短信的话，“我”字需要先按一下9键，再按3下6键，所以，现在想要重新布局每个键上的字母数，让最后的那个值最小，也就是说给你L个字母出现频率，让你将其分布在K个键上，字母顺序不可以变，每个字母出现的频率乘上他所在键的位置，再加总和最小即可。如果有多个解，尽量将字母往后边的键安排。
思路 ：表示比赛的时候根本没看出这是DP，没反应过来，比完了才知道。。。这道DP不太好想，正好看了一个大神的博客，http://www.cnblogs.com/skyivben/archive/2011/11/09/2243068.html ，讲的很详细，可以参考一下。
#include#include #include using namespace std ;int cost[200][200],price[200][200],indexx[200][200] ;void print(int K,int L,char key[],char let[]){ if( K == 0 ) return ; print(K-1, L-indexx[K][L],key,let) ; printf("%c: ",key[K-1]) ; for(int i = L-indexx[K][L] ; i < L ; i++) putchar(let[i]) ; puts("") ;}int main(){ int T ; scanf("%d",&T) ; int K,L ,a[200] ,cnt = 0; while(T--) { char key[200],let[200] ; cnt++ ; scanf("%d %d %s %s",&K,&L,key,let) ; for(int i = 0 ; i < L ; i++) scanf("%d",&a[i]) ; memset(price,0x40,sizeof(price)) ; price[0][0] = 0 ; for(int i = 1 ; i <= L ; i++) for(int j = i ; j <= L ; j++) cost[i][j] = cost[i][j-1]+(j-i+1)*a[j-1] ; for(int i = 1 ; i <= K ; i++) for(int j = i ; j <= L ; j++) for(int k = 1 ; k <= j-i+1 ; k++) { if(price[i-1][j-k] + cost[j-k+1][j] <= price[i][j]) price[i][j] = price[i-1][j-k] + cost[j-k+1][j],indexx[i][j] = k ; } printf("Keypad #%d:\n",cnt) ; print(K,L,key,let) ; printf("\n") ; } return 0 ;}