简单思路:
就是 LIS, 最长上升子序列, 当然把条件改一下, 从模板里的 A[i]> A[ j ] 变成 ss[ i ].find(ss[ j ])==0; 即可. 好好理解最长上升子序列. 是不是和题目中的最长连续单词呢?(自己瞎叫的名字)
ac 代码:
- #include<iostream>
- #include<string>
- using namespace std;
- #define max(a, b) (a)>(b)?(a):(b)
- string ss[2001];
- int dp[2001];
- int main()
- {
- int n;
- cin>> n;
- for (int i = 0; i <n; ++i)
- cin>> ss[i];
- int ans = 0;
- for (int i = 0; i < n; ++i)
- {
- dp[i] = 1;
- for (int j = 0; j < i;++j)
- if (ss[i].find(ss[j]) == 0) dp[i] = max(dp[j] + 1, dp[i]);
- ans = max(ans, dp[i]);
- }
- cout << ans << endl;
- }
来源: http://www.bubuko.com/infodetail-2730639.html