阿里笔试（3.20）第二题讨论= =
感谢@叶挽秋 朋友的指导，我更新了一下答案：
/*
dp法，时间复杂度O(n + 26*26), 空间复杂度O(26*26)。
记录sco[i]，代表此时末位为a~z每一种字母时，可以组成的最大长度
*/
//跳过不满足非递减字符串
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
using namespace std;
bool illegal(string s1) {
int i;
for(i = 1; i < s1.length(); i++) {
if(s1[i] - s1[i-1] < 0) {
return 0;
}
}
return 1;
}
void updateStrings(vector<vector<int> > &srecord, string s1) {
if(illegal(s1)) {
if(s1[0] == s1[s1.length()-1]) {
srecord[s1[0] - 'a'][s1[s1.length()-1] - 'a'] =
srecord[s1[0] - 'a'][s1[s1.length()-1] - 'a'] + int(s1.length());
}
else {
srecord[s1[0] - 'a'][s1[s1.length()-1] - 'a'] =
max(srecord[s1[0] - 'a'][s1[s1.length()-1] - 'a'], int(s1.length()));
}
}
return;
}
//记录最大长度
int maxlen(vector<vector<int> > &srecord) {
int start, end;
int sco[26] = {0};
for(end = 0; end < 26; end++) {
for(start = 0; start <= end; start++) {
sco[end] = max(sco[end], sco[start] + srecord[start][end]);
}
}
return sco[25];
}
int main() {
int n;
cin>>n;
int i;
string s1;
vector<vector<int> > srecord;
vector<int> rtmp;
for(i = 0; i < 26; i++) {
rtmp.push_back(0);
}
for(i = 0; i < 26; i++) {
srecord.push_back(rtmp);
}
for(i = 0; i < n; i++) {
cin>>s1;
updateStrings(srecord, s1);
}
cout<<maxlen(srecord)<<endl;
return 0;
}
——————————————————————————————————————————————————————
没有参加笔试……看了一下讨论区，不知道题目理解的对不对，按照如下理解写了一段代码= =求指导。
理解的题目：只有a-z这26个字母组成的字符串集合，每个只能最多用1次，求能组成的最长的字母序非递减串。
原解答：
#阿里实习##阿里巴巴##笔试题目##include<iostream>
#include<string>
#include<vector>
#include<math.h>
using namespace std;
/*
dp法，时间复杂度O(n*26), 空间复杂度O(26)。
记录sco[i]，代表此时末位为a~z每一种字母时，可以组成的最大长度
*/
//跳过不满足非递减字符串
bool illegal(string s1) {
int i;
for(i = 1; i < s1.length(); i++) {
if(s1[i] - s1[i-1] < 0) {
return 0;
}
}
return 1;
}
//记录最大长度
int maxlen(vector<string> &sing) {
sort(sing.begin(), sing.end());
int i, j;
int sco[26] = {0};
int start, end, maxv;
for(i = 0; i < sing.size(); i++) {
if(illegal(sing[i])) {
start = sing[i][0] - 'a'; //当前单词首字母
end = sing[i][sing[i].length()-1] - 'a'; //当前单词尾字母
maxv = 0;
for(j = 0; j <= start; j++) {
maxv = max(maxv, sco[j]);
//能加入此单词的前面的尾字母有哪些，最长是多少
}
for(j = end; j < 26; j++) {
sco[j] = max(sco[j], maxv + int(sing[i].length()));
//加入此单词的后，尾字母大于等于当前单词的长度都做更新
}
}
}
return sco[25];
}
int main() {
int n;
cin>>n;
int i;
vector<string> sing;
string s1;
for(i = 0; i < n; i++) {
cin>>s1;
sing.push_back(s1);
}
cout<<maxlen(sing)<<endl;
return 0;
}