大概就是把LIS中的能否连接的判断改成string i是否是string j的一个扩展串。
WA了无数，突然想起来应该保证第一个选取初始串。
于是应该对DP数组采用向后更新的方式，筛去所有为0的状态，
因为0代表没有从初始串更新来，所以用它作为第一个串是不合法的。
解决了不合法状态的源头，一切就变得简单了。

代码：

#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1005;
string str[N];
int n, dp[N], ans = 1;
bool cmpStr(string s1, string s2) {
	return s1.length() < s2.length();
}
bool match(int x, int y) {
	if (str[x].length() != str[y].length() + 1)return false;
	int i = 0, j = 0;
	while (i < (signed)str[x].length())
		j += (str[x][i] == str[y][j]), i++;
	return j == (signed)str[y].length();
}
signed main(void) {
	ios::sync_with_stdio(false);
	cin >> n >> str[0];
	for (int i = 1; i <= n; i++)cin >> str[i];
	sort(str + 1, str + 1 + n, cmpStr);
	memset(dp, 0, sizeof(dp)), dp[0] = 3;
	for (int i = 0; i < n; i++)if (dp[i])
		for (int j = i + 1; j <= n; j++)if (match(j, i))
			dp[j] = max(dp[j], dp[i] + 1);
	for (int i = 2; i <= n; i++)ans = dp[i] > dp[ans] ? i : ans;
	cout << str[ans] << endl;
}

• Re:哇，居然只有30行！ (8) yousiki 2016-07-28 12:06:13