#include <iostream>
#include <string>
using namespace std;

struct DPDATA
{
    int w;
    int state[15];
};

int f(string s1, string s2)
{
    int i, j, l;
    int len = s1.length();
    string tmp;
    for (l=len; l>=1; l--)
    {
        for (i=0; i<len-l+1; i++)
        {
            tmp = s1.substr(i, l);
            if (s2.find(tmp) != string::npos)
                return l;
        }
    }
    return 0;
}

int main()
{
    string s[15];
    DPDATA dp[15][15];
    int n;
    int i, j, k;
    int tmpW, b, t;
    int ans;

    while (cin >> n)
    {
        if (n <= 0) break;
        for (i=1; i<=n; i++)
            cin >> s[i];
                  
        for (i=1; i<=n; i++)
        {
            dp[1][i].w = 0;
            for (j=1; j<=n; j++)
                dp[1][i].state[j] = 0;
            dp[1][i].state[i] = 1;
        }       
        
        for (i=2; i<=n; i++)
        {        
            for (j=1; j<=n; j++)
            {
                tmpW = 0;
                b = 0;
                for (k=1; k<=n; k++)
                {
                    t = f(s[k], s[j]);
                    if (dp[i-1][k].state[j] == 0 && tmpW < dp[i-1][k].w + t)
                    {
                        tmpW = dp[i-1][k].w + t;
                        b = k;
                    }
                }
                dp[i][j].w = tmpW;
                for (k=1; k<=n; k++)
                    dp[i][j].state[k] = dp[i-1][b].state[k];
                dp[i][j].state[j] = 1;
            }
        }    
       /* for (i=1; i<=n; i++)
        {
            for (j=1; j<=n; j++)
                cout << dp[i][j].w << ' ';
            cout << endl;
        }*/
        ans = dp[n][1].w;
        for (i=2; i<=n; i++)
        {
            if (ans < dp[n][i].w)
                ans = dp[n][i].w;
        }
        cout << ans << endl;
    }
    
	system("pause");
	return 0;
}

• Re:why DP wa....盯着代码看了4小时了， 还是找不到错误, 大家帮帮忙看看， 行个好心啊(附代码) (2152) __sunshine 2008-09-25 16:27:25
• Re:我 也 这样DP 的 ，，怎么是WA 额 (2) __sunshine 2008-09-25 16:28:27