题目：https://www.nowcoder.com/question/next?pid=16516564&qid=362292&tid=24192838
解法一：dp,过程有点繁琐，主要是集合的有关运算
#include <bits/stdc++.h>
using namespace std;
class Feature{
public:
int x;
int y;
Feature():x(0),y(0){
}
Feature(int _x,int _y):x(_x),y(_y){
}
/*当用set存储自定义类型数据时
需要重载<操作符，用于指定数据在set内的排序准则
set的插入过程:
其实，set容器在判定已有元素a和新插入元素b是否相等时，是这么做的：
1）将a作为左操作数，b作为有操作数，调用比较函数，并返回比较值
2）将b作为左操作数，a作为有操作数，再调用一次比较函数，并返回比较值
如果1、2两步的返回值都是false，则认为a、b是相等的，则b不会被插入set容器中
如果1、2两步的返回值都是true，则可能发生未知行为
因此，记住一个准则：永远让比较函数对相同元素返回false
*/
bool operator < (const Feature &f) const{
if(this->x == f.x)
return this->y < f.y;
return this->x < f.x;
}
};
class Frame{
public:
int num;
vector<Feature> features;
};
void HasCommon(vector<Feature> &f1,vector<Feature> &f2,vector<Feature> &ret){
ret.clear();
if(f1.size() == 0 || f2.size() == 0)
return;
set<Feature> set1;
for(auto i:f1)
set1.insert(i);
set<Feature> set2;
for(auto i:f2)
set2.insert(i);
set<Feature> common;
set_intersection(set1.begin(),set1.end(),set2.begin(),set2.end(),inserter(common,common.begin()));
for(auto f:common)
ret.push_back(f);
}
int func(vector<Frame> &frames){
int sz = frames.size();
/*dp[i]表示以frames[i]结尾的最长连续特征*/
vector<int> dp(sz,0);
for(auto i = 0;i < sz;++i)
dp[i] = frames[i].num != 0 ? 1 : 0;
int ans = dp[0];
for(auto i = 1;i<sz;++i){
if(dp[i] == 0)
continue;
int j = i - 1;
vector<Feature> common;
HasCommon(frames[j].features,frames[i].features,common);
while(j >= 0 && common.size() > 0){
--j;
vector<Feature> tmp(common.size());
copy(common.begin(),common.end(),tmp.begin());
HasCommon(tmp,frames[j].features,common);
}
dp[i] = i - j;
ans = max(ans,dp[i]);
}
return ans;
}
int main(){
int N,M;
cin >> N;
for(auto i = 0;i < N;++i){
cin >> M;
vector<Frame> frames(M);
for(auto j = 0;j < M;++j){
Frame tmp;
cin >> tmp.num;
tmp.features.resize(tmp.num);
for(auto k = 0;k < tmp.num;++k){
cin >> tmp.features[k].x;
cin >> tmp.features[k].y;
}
frames[j] = tmp;
}
cout<<func(frames)<<endl;
}
return 0;
}
解法二：哈希，把每个二维特征(x,y)映射成一个数字
#include <bits/stdc++.h>
using namespace std;
class Frame{
public:
int num;
vector<pair<int,int>> features;
};
int func(vector<Frame> &frames){
int sz = frames.size();
/*记录到上一帧为止最大连续特征数量*/
map<uint64_t,int> cnt;
/*这里有个假设：对于两个特征(x1,y1),(x2,y2)
A*x1 + y1 = A*x2+y2当且仅当 x1 = x2,y1=y2 */
const uint64_t A = 10000481;
int cur = 0,ret = 1;
uint64_t key;
for(auto i = 0;i < sz;++i){
cur = frames[i].num;
if(cur == 0)
continue;
map<uint64_t,int> tmp;
for(auto j = 0;j < cur;++j){
key = A * frames[i].features[j].first + frames[i].features[j].second;
if(cnt.find(key) != cnt.end()){
tmp[key] = cnt[key] + 1;
ret = max(ret,tmp[key]);
}
else
tmp[key] = 1;
}
cnt = tmp;
}
return ret;
}
int main(){
int N,M;
cin >> N;
for(auto i = 0;i < N;++i){
cin >> M;
vector<Frame> frames(M);
for(auto j = 0;j < M;++j){
Frame tmp;
cin >> tmp.num;
tmp.features.resize(tmp.num);
for(auto k = 0;k < tmp.num;++k){
cin >> tmp.features[k].first;
cin >> tmp.features[k].second;
}
frames[j] = tmp;
}
cout<<func(frames)<<endl;
}
return 0;
}
解法三：https://blog.csdn.net/wwxy1995/article/details/89463465
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> FEATURE;
class Frame{
public:
int num;
vector<FEATURE> features;
};
int func(vector<Frame> &frames){
int sz = frames.size();
/*记录每一个特征的上一次帧索引*/
map<FEATURE,int> lastIndex;
/*记录每一个特征最大连续次数*/
map<FEATURE,int> cnt;
for(auto i = 0;i<frames[0].num;++i){
lastIndex[frames[0].features[i]] = 0;
cnt[frames[0].features[i]] = 1;
}
int ret = 1;
for(auto i = 1;i < sz;++i){
for(auto j = 0;j<frames[i].features.size();++j){
if(lastIndex[frames[i].features[j]] == i-1)
cnt[frames[i].features[j]] += 1;
else
cnt[frames[i].features[j]] = 1;
lastIndex[frames[i].features[j]] = i;
ret = max(ret,cnt[frames[i].features[j]]);
}
}
return ret;
}
int main(){
int N,M;
cin >> N;
for(auto i = 0;i < N;++i){
cin >> M;
vector<Frame> frames(M);
for(auto j = 0;j < M;++j){
Frame tmp;
cin >> tmp.num;
tmp.features.resize(tmp.num);
for(auto k = 0;k < tmp.num;++k){
cin >> tmp.features[k].first;
cin >> tmp.features[k].second;
}
frames[j] = tmp;
}
cout<<func(frames)<<endl;
}
return 0;
}
