这道题明显可以两重循环搞定。很简单的二维dp,但qq群里的人嚷着必须三重。废话不说上代码。
#if __GNUC__>2 #include <ext/hash_map> using namespace __gnu_cxx; #else #include <hash_map> using namespace stdext; #endif #include <iostream> #include <vector> #include <algorithm> using namespace std; // using namespace stdext; int cal(vector<int> t){ sort(t.begin(),t.end()); typedef hash_map<int,int> MAP; vector<MAP> ms(t.size(), MAP()); int _max=0; for(int i=0;i<t.size();i++){ for(int j=0;j<i;j++){ int d=t[i]-t[j]; if(ms[j].find(d)==ms[j].end()){ ms[i][d]=2; } else ms[i][d]=ms[j][d]+1; _max=max(_max,ms[i][d]); } } return _max; } int main(){ vector<int> t; t.push_back(-1); t.push_back(1); t.push_back(3); t.push_back(3); t.push_back(3); t.push_back(2); t.push_back(1); t.push_back(0); cout<<cal(t)<<endl; return 0; }
上面的hashmap查找find,理论上是常数时间。换成map的话,总复杂度就变成n^2*lgn.