题意：给出m个长度为3的由0~9组成的字符串，每个字符串有一个权值，可正可负。要求构造出一个长度为n的字符串，若字符串中包含题目给出的某个字符串，则获得该字符串的权值。求一个权值最大的字符串。
分析：其实很早就想到了记录当前位和上一位的数字的dp方程，但是由于没理解题目意思(貌似题目说的也不太清楚)，所以不确定如果包含同一个字符串多次，该字符串的权值是只算一次还是算多次。在网上看了看他人的解答，原来是按算多次来理解的。于是下手写，细想的时候发现顺推不能保证字典序最小，于是加了个string记录，还是顺推，果断超时了。才想到从右往左倒着dp，就能保证最后得出的字符串是字典序最小的了，这一点想一想dp时循环的顺序就很容易理解了。
用f[now][i][j]表示从右往左到第now位，且第now位上数字为i,第now-1位上的数字为j的最大值，则f[now][i][j]=max{
f[now-1][j][k]+w[100*i+10*j+k] }
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <stdlib.h>
#include <limits.h>
using namespace std;
#define inf INT_MAX

int f[10010][10][10],pre[10010][10][10],n,m,w[1010],out[10010];

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++)  // dp
        {
            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);
    }
    return 0;
}