洛谷P1481：最长不下降子序列

P1481是最长不下降子序列的中二版。一个词是否为另一个词的序列，看是否为他的前缀。这里有点小坑的问题在于DP的一些特性。

此处的坑在于，DP（记忆化搜索）的特性需求：

• 数据被使用之前需要已经被算出来
• 递归子式不能有后效性

所以，第二层递归从小到大，会遇到未计算的情况。

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

int n;
int* dp;
string* strs;
int common(string a, string b) {
  int res = 0;
  int len = (a.size() < b.size()) ? a.size() : b.size();
  for (size_t i = 0; i < len; i++) {
    if (a[i] == b[i]) {
      res++;
    } else {
      return 0;
    }
  }
  return res;
}

int main() {
  ios::sync_with_stdio(0);
  cin >> n;
  strs = new string[n + 1];
  dp = new int[n + 1];
  memset(dp, 0, sizeof(int) * (n + 1));
  int ans = 1;
  for (int i = 1; i <= n; i++) {
    cin >> strs[i];
  }
  dp[1] = 1;
  for (int i = 2; i <= n; i++) {
    for (int j = i; j >= 1; j--) {
      if (strs[i].find(strs[j]) == 0) {
        dp[i] = max(dp[i], dp[j] + 1);
        ans = max(ans, dp[i]);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    cout << dp[i + 1] << ' ';
  }

  cout << ans << endl;
  delete[] strs;
  return 0;
}