首页 > 试题广场 >

特征提取

[编程题]特征提取
  • 热度指数:12577 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
       小明是一名算法工程师,同时也是一名铲屎官。某天,他突发奇想,想从猫咪的视频里挖掘一些猫咪的运动信息。为了提取运动信息,他需要从视频的每一帧提取“猫咪特征”。一个猫咪特征是一个两维的vector<x, y>。如果x_1=x_2 and y_1=y_2,那么这俩是同一个特征。
       因此,如果喵咪特征连续一致,可以认为喵咪在运动。也就是说,如果特征<a, b>在持续帧里出现,那么它将构成特征运动。比如,特征<a, b>在第2/3/4/7/8帧出现,那么该特征将形成两个特征运动2-3-4 和7-8。
现在,给定每一帧的特征,特征的数量可能不一样。小明期望能找到最长的特征运动。

输入描述:
第一行包含一个正整数N,代表测试用例的个数。

每个测试用例的第一行包含一个正整数M,代表视频的帧数。

接下来的M行,每行代表一帧。其中,第一个数字是该帧的特征个数,接下来的数字是在特征的取值;比如样例输入第三行里,2代表该帧有两个猫咪特征,<1,1>和<2,2>
所有用例的输入特征总数和<100000

N满足1≤N≤100000,M满足1≤M≤10000,一帧的特征个数满足 ≤ 10000。
特征取值均为非负整数。


输出描述:
对每一个测试用例,输出特征运动的长度作为一行
示例1

输入

1
8
2 1 1 2 2
2 1 1 1 4
2 1 1 2 2
2 2 2 1 4
0
0
1 1 1
1 1 1

输出

3

说明

特征<1,1>在连续的帧中连续出现3次,相比其他特征连续出现的次数大,所以输出3

备注:
如没有长度大于2的特征运动,返回1
/*深度优先遍历的思想DFS
每一帧的特征只和下一层的相同特征相连*/
#include 
(849)#include 
#include 
(849)#include 
#include 
(849)#include 
using namespace std;
int N,M;
int maxn = 10001;
struct feature{
    int x;
    int y;
};
int max_features=1, cur_max_frame=0;
void DFS(feature f, int cur_frame, vector video[], int ans){
    if(cur_frame>cur_max_frame)
        cur_max_frame = cur_frame;
    if(cur_frame>M-1)
        return;
    for(int i=0;i<video[cur_frame].size();i++){
        feature tmp = video[cur_frame][i];
        if(f.x==tmp.x && f.y==tmp.y){
            if(ans+1>max_features){
                max_features = ans+1;
            }
            DFS(tmp, cur_frame+1, video, ans+1);
        }
    }
}
int main()
{
    scanf("%d", &N);
    while(N>0){
        N--;
        max_features=1, cur_max_frame=0;
        scanf("%d", &M);
        vector video[M];
        for(int i=0;i<M;i++){
            int feature_num;
            scanf("%d", &feature_num);
            for(int j=0;j<feature_num;j++){
                feature f;
                scanf("%d %d",&f.x, &f.y);
                video[i].push_back(f);
            }
        }
        int cur = 0;
        while(cur<M-1){
            if(video[cur].size()==0){
                cur++;
                continue;
            }
            for(int i=0;i<video[cur].size();i++){
                feature f = video[cur][i];
                DFS(f, cur+1, video, 1);
            }
            cur = cur_max_frame;
        }
        printf("%d\n", max_features);
    }
    return 0;
}
发表于 2020-04-11 11:26:52 回复(0)
# 看不懂题目的测试用例和题目的具体用意,感觉这个题目有问题,求大佬解答
N = int(input()) # 测试用例的个数
M = int(input()) # 视频的帧数
frame = []
for i in range(M):
    frame.append(list(map(int, input().split(' '))))

maxFrame = []
cnty = 0
numy = []
for i in range(M):
    if frame[i][0] == 0:
        continue
    else:
        cntx = 0
        numx = frame[i][1]
        for j in range(2, len(frame[i])):
            # 若该帧下一个数与上一个数相等,且不为零,那么就加1,否则进行下一轮判断
            if numx == frame[i][j] and frame[i][j] != 0:
                cntx += 1
                numx = frame[i][j]
            else:
                numx = frame[i][j]
        # 每一帧的计算的特征数
        maxFrame.append(cntx)
        numx = frame[i][1]
        # 记录每帧的连续点,不重复
        for j in range(2, len(frame[i])):
            if numx == frame[i][j]:
                numy.append((numx, frame[i][j]))
                break
            else:
                numx = frame[i][j]
# 计算连续的帧中连续出现的次数
tlp = numy[0]
for t in numy:
    if tlp == t:
        cnty += 1
    else:
        cnty = 0
    maxFrame.append(cnty)
print(max(maxFrame))

发表于 2019-08-28 15:01:41 回复(0)

C++

//哈希表
#include<iostream>
#include<unordered_map>

using namespace std;

struct Vector {
    int x;
    int y;

    Vector(int x, int y = 0) : x(x), y(y) {}
    Vector() = default;

    bool operator==(const Vector& other) const {
         return x == other.x && y == other.y;
    }
};

struct hash_func {
    size_t operator() (Vector v) const {
        return size_t(v.x + v.y);
    }
};

int main() {
    int T;
    cin >> T;
    while (T--) {
        int m, n;
        cin >> m;
        int maxCount = 0;
        unordered_map<Vector, int, hash_func> hash, prehash;
        while (m--) {
            cin >> n;
            for (int i = 0; i < n; ++i) {
                int x, y;
                cin >> x >> y;
                Vector v(x, y);
                if (prehash.find(v) != prehash.end()) {
                    hash[v] = prehash[v] + 1;
                } else {
                    hash[v] = 1;
                }
                maxCount = max(maxCount, hash[v]);
            }
            prehash = hash;
            hash.clear();
        }
        cout << maxCount << endl;
    }
    return 0;
}
发表于 2021-03-06 15:39:31 回复(0)
用字典记录每个特征出现的帧数,然后逐个计算每个特征连续出现的最大帧数
from collections import defaultdict

def longest_frame(frames):
    n = len(frames)
    left, right = 0, 1
    longest = 1
    while left < n - 1:
        while right < n:
            if frames[right] == frames[right - 1] + 1:
                longest = max(longest, frames[right] - frames[left] + 1)
            else:
                left = right
                right += 1
                break
            right += 1
        if right == n:
            break
    return longest

if __name__ == "__main__":
    N = int(input())
    for _ in range(N):
        M = int(input())
        # 记录特征出现的帧编号
        feature_dict = defaultdict(lambda: [])
        for frame in range(M):
            row = list(map(int, input().split()))
            fea_num = row[0]
            if fea_num == 0:
                continue
            row = row[1:]
            for i in range(0, len(row), 2):
                feature_dict[(row[i], row[i + 1])].append(frame)
        max_len = 0
        for feature in feature_dict:
            frame_list = feature_dict[feature]
            # 双指针求最长连续帧长度
            max_len = max(max_len, longest_frame(frame_list))
        print(max_len)


发表于 2021-01-25 17:47:51 回复(0)
#include<iostream>
#include<vector>
#include <algorithm>
#include<map>
using namespace std;
int main() {
    int n, m, num;
    vector<int> ret = { 0 };
    pair<int, int> vec;
    cin >> n >> m;
    for(int i = 0; i < n; i++) {      //遍历每一个输入样例
        map<pair<int, int>, int> max;    //保存全局最大值
        vector<pair<int, int>> last[2];    //保存连续两个视频帧的特征向量
        map<pair<int, int>, int> val;    //保存以当前帧为结束的出现次数
        for(int j = 0; j < m; j++) {
            cin >> num;
            last[j % 2].clear();     //为保存最新的输入做准备
            for(int k = 0; k < num; k++) {
                if(num == 0) break; //如果输入的特征向量个数为零,使用for循环还是会进入循环内部,可以用while来优化
                cin >> vec.first >> vec.second;  //输入每一个特征向量
                last[j % 2].push_back(vec);         //保存是为了下次输入特征向量时可以回溯之前是否出现过
                vector<pair<int, int>>::iterator it = find(last[(j + 1) % 2].begin(), last[(j + 1) % 2].end(), vec);  //判断之前的当前的特征向量是否在之前出现过
                if(it != last[(j + 1) % 2].end()) { //出现过,则在当前帧为结束的出现次数加一,并更新全局的最大值
                    val[vec]++;
                    max[vec] = max[vec] > val[vec] ? max[vec] : val[vec];
                }
                else{                                      //没有出现过,则在当前帧为结束的出现次数为一,并更新全局的最大值
                    val[vec] = 1;
                    max[vec] = max[vec] > val[vec] ? max[vec] : val[vec];
                }
            }
        }
        for(map<pair<int, int>, int>::iterator it = max.begin(); it != max.end(); it++) {  //一个输入样例中的最大值
            if(it->second > ret[i]) {
                ret[i] = it->second;
            }
        }
    }
    for(inti = 0; i < n; i++)
        cout << ret[i] << endl;
    return0;
}


发表于 2020-07-18 15:44:26 回复(0)
从头到尾遍历
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i=0;i<n;i++){
            int m = in.nextInt();
            Pair[][] pairs = new Pair[m][];
            for (int j=0;j<m;j++){
                int t = in.nextInt();
                pairs[j] = new Pair[t];
                for (int k=0;k<t;k++){
                    pairs[j][k] = new Pair(in.nextInt(),in.nextInt());
                }
            }
            int max = Integer.MIN_VALUE;
            for (int j=0;j<m;j++){          //遍历每一帧
                for (int k=0;k<pairs[j].length;k++){         //遍历每一特征
                    if (pairs[j][k] != null){         //如果特征不为null
                        int c = 1;          //特征初始次数为1
                        int temp = c;
                        for (int t=j+1;t<m;t++){         //遍历当前帧以下的所有帧
                            for (int s = 0;s<pairs[t].length;s++){      //遍历每一特征
                                if (pairs[t][s] != null && pairs[j][k].first == pairs[t][s].first
                                        && pairs[j][k].second == pairs[t][s].second){     //若特征不为null,且相等
                                    pairs[t][s] = null;         //将其标志为null,防止后序重复遍历
                                    c++;      //特帧数加1
                                }
                            }
                            if (temp == c){    //遍历一个帧后,特征数不变,说明其已不连续了,此时退出
                                break;
                            }else {
                                temp = c;
                            }
                        }//还有一种退出情况,即循环到尾部,自动退出了
                        if (c > max)
                            max = c;    //记录最大特帧数
                    }
                }
            }
            System.out.println(max);
        }
    }

    private static class Pair{
        int first;
        int second;
        Pair(int first,int second){
            this.first = first;
            this.second = second;
        }
    }
}


编辑于 2019-08-18 16:04:57 回复(0)
#把特征出现的帧记录在字典中,并取最长连续帧
n =int(input())
for i in range(n):
    m =int(input())
    #保存不同的帧出现的像素
    num =0
    index =0
    #保存不同特征出现的位置
    dic ={}
    while index < m:
        line =[int(x) forx in input().strip().split()]
        num_pixel =line[0]
        num +=num_pixel
        p =[]
        for j in range(num_pixel):
            term =(line[2*j+1],line[2*j+2])
            if term not in dic:
                dic[term] =[]
                dic[term].append(index)
            else:
                dic[term].append(index)
        index +=1
    #最大连续序列
    max1 =0#全局最大长度
    for key indic:
        sequence =dic[key]
        max2 =1#至少有一个
        s =0
        while s +1< len(sequence):
            if sequence[s+1] ==sequence[s] +1:
                max2 +=1
            else:
                #连续断了,新断归0
                max2 =1
            if max2 > max1:
                max1 =max2
            s +=1
        if max2 > max1:
            max1 =max2
    print(max1)

发表于 2019-08-11 11:01:34 回复(0)
#include<iostream>
#include<vector>
#include<map>
#include<set>
using namespace std;

int main(){
    int N; cin>>N;
    for(int i=0; i<N; i++){
        int M; cin>>M;
        
        int ans = 0;
        map<pair<int,int>, int> pairMap;
        
        vector<set<pair<int,int>>> nums(M);
        for(int i=0; i<M; i++){
            set<pair<int,int>> one;
            int len; cin>>len;
            int x, y;
            for(int j=0; j<len; j++){
                cin>>x>>y; one.insert(make_pair(x,y));
                if(i-1>=0 && nums[i-1].find(make_pair(x,y))!=nums[i-1].end()){
                    pairMap[make_pair(x,y)]++;
                }else{
                    pairMap[make_pair(x,y)] = 1;
                }
                ans = max(ans, pairMap[make_pair(x,y)]);
            }
            nums[i] = one;
        }
        cout<<ans<<endl;
    }
    return 0;
}

发表于 2019-07-07 18:30:34 回复(1)
用Map做,省事很多!!!

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main()
{
    int n, m;
    cin >> n;

    int len;
    pair<int, int> xy;

    while (n--)
    {
        cin >> m;

        int maxCnt = 0;
        map<pair<int, int>, int> preFeaTimes;
        map<pair<int, int>, int> feaTimes;
        while (m--)
        {
            cin >> len;
            for (int i = 0; i < len; i++)
            {
                cin >> xy.first >> xy.second;
                
                if (preFeaTimes.count(xy))
                    feaTimes[xy] = preFeaTimes[xy] + 1;
                else
                    feaTimes[xy] = 1;

                if (feaTimes[xy] > maxCnt)
                    maxCnt = feaTimes[xy];
            }
            preFeaTimes.clear();
            preFeaTimes.swap(feaTimes);
        }
        cout << maxCnt << endl;
    }

    return 0;
}




发表于 2019-08-29 11:21:57 回复(12)
我想知道有什么方法能让一个数组中的数的组合成为map的键值。做题的时候没想到,只能把数组转换程字符串作为map的键值了。很难受
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        for(int i = 0; i < N; ++i){
            HashMap<String, Integer> mem = new HashMap<>();
            HashMap<String, Integer> temp_mem = new HashMap<>();
            int M = sc.nextInt();
            int max = 1;
            for(int j = 0; j < M; ++j){
                temp_mem.clear();
                int n = sc.nextInt();
                for(int k = 0; k < n; ++k){
                    int x = sc.nextInt();
                    int y = sc.nextInt();
                    String key = String.valueOf(x) + " " + String.valueOf(y);
                    temp_mem.put(key, mem.getOrDefault(key, 0) + 1);
                    max = Math.max(temp_mem.get(key), max);
                }
                mem.clear();
                mem.putAll(temp_mem);
            }
            if(max <= 1){
                System.out.println(1);
            }else{
                System.out.println(max);
            }
        }

    }
}




发表于 2019-08-09 21:45:28 回复(24)
基本的想法是这样的,比如案例数据:
1
8
2 1 1 2 2
2 1 1 1 4
2 1 1 2 2
2 2 2 1 4
0
0
1 1 1
1 1 1
使用map记录动作上一次出现的帧数和当前连续帧数,同时记录下当前连续的最长帧数res。
第一组数:(1,1)-> (0,1)    ,    (2,2) -> (0,1)      res = 1;
即代表(1,1)上次出现在0时刻,当前连续动作为1;(2,2)上次出现在0时刻,当前连续动作为1
第二组数:(1,1)-> (1,2)    ,    (1,4) -> (1,1)      res = 2;
即代表(1,1)上次出现在1时刻,当前连续动作为2;(1,4)上次出现在1时刻,当前连续动作为1
第三组数:(1,1)-> (2,3)    ,    (2,2) -> (2,1)      res = 3;
即代表(1,1)上次出现在2时刻,当前连续动作为3;(2,2)上次出现在2时刻,当前连续动作为1
第四组数:(2,2)-> (3,2)    ,    (1,4) -> (3,1)      res = 3;

代码如下:(实际上需要写个while(N--),但是好像测试用例都是1组,就懒得改了)
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;

int main() {
    int N; cin >> N; //测试用例数
    int M; cin >> M; //帧数
    map<pair<int, int>, pair<int, int> > record;

    int amounts, x, y;
    int res = 1;
    for (int i = 0; i < M; i++) {//每一组测试用例
        cin >> amounts;
        for (int j = 0; j < amounts; j++) { //每一组特征
            cin >> x >> y;
            if (record.find(make_pair(x, y)) == record.end()) {
                record.insert(make_pair(make_pair(x, y), make_pair(i, 1)));
            }
            else {
                auto iter = record.find(make_pair(x, y));
                if (i - iter->second.first == 1) {//连续出现
                    iter->second.first = i; iter->second.second += 1;
                    res = max(res, iter->second.second);
                }
                else { //没有连续出现
                    iter->second.first = i;
                    iter->second.second = 1;
                }
            }
        }
    }
    cout << res << endl;
    return 0;
}



编辑于 2019-08-08 09:43:24 回复(0)

貌似没啥好说的额,用一个字典记录上一帧最大连续特征就行

n = int(input())

while n > 0:
    m = int(input())
    res = 1
    d = {}
    for i in range(m):
        l = list(map(int , input().split()))
        k = l[0]
        tmp_d = {}
        for j in range(k):
            index = l[2 * j + 1] * 1000000000 + l[2 * j + 2]
            if index in d:
                tmp_d[index] = d[index] + 1
                res = max(res, tmp_d[index])
            else:
                tmp_d[index] = 1
        d = tmp_d
    print(res)
    n -= 1
发表于 2019-05-28 20:45:48 回复(3)
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int ans = 0;
		Map<Reference, Integer> map1 = new HashMap<Reference, Integer>();
		Map<Reference, Integer> map2 = new HashMap<Reference, Integer>();
		for(int i=0;i<n;i++) {
			int m = scanner.nextInt();
			map1.clear();
			for(int j=0;j<m;j++) {
				 int p = scanner.nextInt();
				 if(p==0) {
					 map1.clear();
					 continue;
				 }
				 for(int k=0;k<p;k++) {
					 int x = scanner.nextInt();
					 int y = scanner.nextInt();
					 Reference reference = new Reference(x, y);
					 if(map1.containsKey(reference)) {
						 map2.put(reference, map1.get(reference)+1);
					 }else {
						 map2.put(reference, 1);
					 }
					 ans = Math.max(ans, map2.get(reference));
				 }
				 map1.clear();
				 map1.putAll(map2);
				 map2.clear();
			}
		}
		System.out.println(ans);
	}
	
	
	
	
}
class Reference{
	int x;
	int y;
	public Reference(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
	@Override
	public int hashCode() {
		return  x + y + x*y;
	}
	@Override
	public boolean equals(Object obj) {
		Reference reference = (Reference)obj;
		return x==reference.x && y==reference.y;
	}
	
}

发表于 2019-10-30 16:26:50 回复(1)
import java.util.*;
public class Main
{
    public static void main(String [] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        for(int p=0;p<n;p++) {
            Map <point,Integer> map=new HashMap<>();//map存放(特征值,连续次数)
            int m=in.nextInt();
            int max=0;
            for(int q=0;q<m;q++) {
                int z=in.nextInt();
                ArrayList <point> list=new ArrayList<>();//list存放本行有哪些特征值
                for(int i=0;i<z;i++) {
                    int x=in.nextInt();
                    int y=in.nextInt();
                    point po=new point(x,y);                      for(point poo:map.keySet()) {
                        if(poo.x==x&&poo.y==y) {
                            po=poo;
                            map.put(po, map.get(po)+1);
                            max=Math.max(map.get(po),max);
                            break;
                        }
                    }
                    if(!map.containsKey(po)) {
                        map.put(po,1);
                        max=Math.max(map.get(po),max);
                    }
                    list.add(po);
                }
                for(point poo:map.keySet()) {//对于本行没有出现过的特征值,map对应的键值清零

                    if(!list.contains(poo)) {
                        map.put(poo,0);
                    }
                }
            }
            System.out.println(max);
        }
    }
}
class point {
    int x=0;
    int y=0;
    point(int a,int b) {
        x=a;
        y=b;
    }
}

发表于 2019-09-16 11:37:42 回复(0)
cases = int(input())

for j in range(cases):

    num_frames = int(input())

    count_dict = {}
    max_count = 0

    for f in range(num_frames):  # 对于每一帧
        line = list(map(int, input().split()))
        num_features = line[0]
        features = []
        for i in range(1, num_features * 2, 2):  # 对于一帧中的每个feature
            feature = (line[i], line[i+1])
            features.append(feature)
            if feature in count_dict.keys():
                count_dict[feature] += 1
            else:
                count_dict[feature] = 1
        for key in count_dict.keys():  # 如果该帧中没有某个特征,则这个特征从0开始记数
            if key not in features:
                count_dict[key] = 0
        max_count = max(max_count, max(count_dict.values()))  # 记录最大数

    print(max_count)


python解法,直观地使用dict计数即可,没有特别的技巧
发表于 2022-05-03 08:10:25 回复(0)
用一个map存储所有特征目前已经连续出现的次数,用另一个map存储特征上一次出现时所在的帧号(以便判断当前帧中的特征能不能和之前的连续起来)。
但是用map的时候,因为是二维坐标,我不知道可以用pair来做键值,就想到字符串了,因为C++里面不像JAVA转字符串那么方便,不过好在坐标是用空格隔开的,所以读数据的时候直接读取成string形式,免得后续处理。
#include<iostream>
#include<stdio.h>
#include<vector>
#include<cstring>
#include<map>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--) {
        int m;
        cin>>m;
        map<string,int> rec;//每一特征连续出现的次数
        map<string,int> pre; //特征上次出现的帧号
        int res=0;
        for(int i=0;i<m;i++) {
            int num;
            cin>>num;
            for(int j=0;j<num;j++) {
                string x;
                string y;
                cin>>x;
                cin>>y;
                string cur=x+"#"+y;
                if(pre.count(cur)==0 || pre[cur]!=i-1) {
                    rec[cur]=1;
                } else {
                    //与上一次连续
                    rec[cur]++;
                }
                 pre[cur]=i;
                res=max(res,rec[cur]);
            }
        }
        cout<<res<<endl;
    }
    return 0;
}


编辑于 2021-04-11 16:52:42 回复(0)
Java解法
import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int num = scanner.nextInt();
        HashMap<String, Integer> last = new HashMap<>();
        HashMap<String, Integer> current = new HashMap<>();
        int max=0;
        for (int i = 0; i < num; i++) {
            int pairNum = scanner.nextInt();
            for (int j = 0; j < pairNum; j++) {
                String key= scanner.nextInt()+"_"+scanner.nextInt();
                if (last.get(key)==null){
                    current.put(key,1);
                }else {
                    current.put(key,last.get(key)+1);
                }
            }
            for (Integer value : current.values()) {
                max=Math.max(value,max);
            }
            last=current;
            current=new HashMap<>();
        }
        System.out.println(max);
    }
}


发表于 2020-03-01 23:26:25 回复(0)
两个map轻松解决,一个用来保存当前帧的特征,一个用来保存上一帧的特征。用hashmap比treemap更合理,但是C++ 的hashmap不能接受pair作为key 转化成string即可
#include<bits/stdc++.h>
using namespace std;
unordered_map<string, int> last;
unordered_map<string, int> cur;

string make_str(int x, int y) {
	return to_string((long long)x) + to_string((long long)y);
}

int N, M;
int main() {
    scanf("%d", &N);
    while(N--) {
        scanf("%d", &M);
        int res = 1;
        while(M--) {
            int cnt; scanf("%d", &cnt);
            cur.clear();
            while(cnt--) {
                int x, y; scanf("%d%d", &x, &y);
                if(last.count(make_str(x, y))) {
                    cur[make_str(x, y)] += (last[make_str(x, y)] + 1);
                    res = max(res, cur[make_str(x, y)]);
                } else {
                    cur[make_str(x, y)]++;
                }
            }
            last = cur;
        }
        last.clear();
        printf("%d\n", res);
    }
}
/*
1
8
2 1 1 2 2
2 1 1 1 4
2 1 1 2 2
2 2 2 1 4
0
0
1 1 1
1 1 1
res: 3
*/


发表于 2019-12-28 10:27:17 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m,k,Max=1,x,y;
    cin>>n;
    while(n--){
        cin>>m;
        map<pair<int,int>, int> M, T;
        for(int i=1;i<=m;i++){
            cin>>k;
            for(int j=0;j<k;j++){
                pair<int,int> p;
                cin>>p.first>>p.second;
                if(M.find(p)==M.end())    
                    T[p] = 1;
                else{
                    if(M[p]==i-1){
                        T[p]++;
                        Max = max(Max, T[p]);
                    }else
                        T[p] = 1;
                }
                M[p] = i;
            }
        }
        cout<<Max<<endl;
    }
    return 0;
}

发表于 2019-09-17 07:55:04 回复(0)
#include<iostream>
#include<map>
using namespace std;

int main(){
    int N;                                         //测试用例
    cin >> N;
    for(int i = 0; i < N; ++i){
        //第 i 个测试数据
        int M;
        cin >> M;                                  //视频帧数
        map<pair<int,int>,int> charact;            //保存到达第 j 帧时,每个特征的最大连续出现次数
        int ans = 0;                               //第 i 个测试数据中,所有特征中最大连续出现次数
        for(int j = 0; j < M; ++j){
            //判断第 i 个测试数据的第 j 帧
            int ln;
            cin >> ln;                             //每一帧的特征数量
            int flameJ = 0;                        //到达第 j 帧时出现的最大连续特征数量
            map<pair<int,int>,int> temp;           //保存中间结果
            for(int k = 0; k < ln; ++k){
                //第 i 个测试数据的第 j 帧的第 k 个特征
                int x,y;
                cin >> x >> y;
                //如果上一帧中有 {x,y} 特征,长度加 1 并保存到 temp 中
                if(charact.count({x,y})){
                    temp[{x,y}] = charact[{x,y}] + 1;
                    flameJ = max(flameJ,charact[{x,y}] + 1);
                }
                //如果没有该帧,那么长度肯定为 1,并保存到 temp 中
                else{
                    temp[{x,y}] = 1;
                    flameJ = max(flameJ,1);
                }
            }
            ans = max(ans,flameJ);              //保存到第 j 帧为止的已知的最长连续特征数量
            charact = temp;                     //更新第 j 帧的状态
        }
        cout << ans << '\n';
    }
    return 0;
}
动态规划思想
使用 map<pair<int,int>,int> dp作为状态记录结构,记录以第 j 帧结尾时,第 j 帧中所有特征连续出现的次数。我们从第 1 帧迭代遍历到最后一帧 M,记录到第 j 帧时所有特征中连续出现次数的最大值为 flameJ,那么这 M 帧中的最大 flameJ 就是我们要找的,所有帧中某个特征连续出现的最大次数。
状态转移方程:
(xj,yj) 表示第 j 帧中的特征,dp 表示状态记录结构,temp 表示中间记录结果。
  • 如果 dp.count({xj,yj}) > 0 ,代表前一帧中存在该特征,先记录该状态 temp[{xj,yj}] = dp[{xj,yj}] + 1,并且与 flameJ 比较,看是不是最大的连续帧,flameJ = max(flameJ, temp[{xj,yj}] );
  • 如果不存在特征 (xj,yj),那么代表前一帧中不存在该帧中,那么到该帧时,(xj,yj) 特征的连续出现次数为 1,记录到 temp[{xj,yj}] = 1,并于 flamej 比较:flameJ = max(flameJ,1)。
最后,返回最大的 flameJ 即可,请参考上面的代码!
编辑于 2021-08-19 15:16:00 回复(1)