美团笔试9.23

AC了const int MAXN = 1e4+5; int a[MAXN], dp[MAXN][MAXN]; int int main(int argc, char const *argv[]) { int n, ans = -1; cin >> n; for(int i = 0; i < n; i ++){ cin >> a[i]; for(int j = 0; j < MAXN; j ++){ dp[i][j] = 1; } } for(int i = 1; i < n; i ++){ for(int j = 0; j < i; j ++){ dp[i][a[j]] = dp[j][a[i]] + 1; ans = max(dp[i][a[j]], ans); } } cout << ans << endl; return 0; }

// 这是我的代码 #include <iostream> (30316)#include <vector> using namespace std; int main() { int n; cin >> n; if (n < 3) { cout << n; return 0; } vector<int> a(n); for(int i = 0; i < n; ++i) { cin >> a[i]; } int res = 2; vector<int> dp(n); // vector<int> idx(n); 应该把长度相同的前一个下标记录在数组里 unordered_map<int, vector<int>> m; dp[0] = 1, dp[1] = 2; m[0] = {-1}, m[1] = {0}; for (int i = 2; i < n; ++i) { for (int j = 0; j < i; ++j) { for (int k = 0; k < m[j].size(); ++k) { if (m[j][k] == -1 || a[m[j][k]] == a[i]) { if (dp[j] + 1 >= dp[i]) { dp[i] = dp[j] + 1; m[i].push_back(j); } } } } res = max(res, dp[i]); } cout << res; return 0; }