感想：难题，这道想了我很久，最后还是参考了别人的博客才懂
注意点：1.字符串的值使用可以用hash实现，最终字符串添加字符需要一个一个添加而不是3个3个添加
2.运用递推关系建立dp方程
3.dp方程从后往前建立，这样可以保证最终字符串最小
代码参考自：
http://www.cppblog.com/Ayue/archive/2011/11/10/159937.html
#include <iostream> #include <stdio.h> #include <memory.h> #include <stdlib.h> #include <iostream> #include <algorithm> #include <limits.h> using namespace std; #define inf INT_MAX int f[10010][10][10],pre[10010][10][10],n,m,w[1010]; int main(){ int i,j,k,ans,p,q,tem,x,y,now; while(scanf("%d%d",&m,&n)!=EOF){ memset(w,0,sizeof(w)); for(i=1;i<=m;i++){ scanf("%d%d",&x,&y); w[x]=y; } for(j=0;j<=9;j++){ for(k=0;k<=9;k++){ f[2][j][k]=0; } } for(now=3;now<=n;now++){ for(i=0;i<=9;i++){ for(j=0;j<=9;j++){ f[now][i][j]=-inf; for(k=0;k<=9;k++){ if(f[now-1][j][k]+w[100*i+10*j+k]>f[now][i][j]){ f[now][i][j]=f[now-1][j][k]+w[100*i+10*j+k]; pre[now][i][j]=k; } } } } } ans=-inf; for(i=0;i<=9;i++){ for(j=0;j<=9;j++){ if(f[n][i][j]>ans){ ans=f[n][i][j]; p=i; q=j; } } } i=n; while(i>2){ printf("%d",p); tem=pre[i][p][q]; p=q; q=tem; i--; } printf("%d%d\n",p,q); } }