2021 CCPC 哈尔滨 B. Magical Subsequence（思维题）

Problem - B - Codeforces

思路：

从前往后找寻两两之和一样的最大长度。可以不连续，但是一定是按从前往后的顺序。可以发现每个数的范围是[1，100]，范围不大，是一个突破口，两数相加的和sum的范围是[2,200]，则遍历sum的每一种情况。当正在遍历的数和之前出现的数相加等于sum时，res+=2，然后将前面的数设置为不能使用。如果正在遍历的数和sum的差在前面没有出现过，则把该数设置为可以使用，继续向后遍历。

代码：

#include<iostream>
#include<cstring>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int vis[205];
int n, maxn;

int main() {
    
    scanf("%d", &n);
    vector<int> a(n);
    

    for(int i = 0; i < n; i ++)   scanf("%d", &a[i]);

    int maxn = -1;
    for(int sum = 2; sum <= 200; sum ++) {
         int res = 0;
         memset(vis, 0, sizeof vis);
        for(int i = 0; i < n; i ++) {
            if(a[i] < sum) {
                if(vis[sum - a[i]]) {
                    res += 2;
                    memset(vis, 0, sizeof vis);
                } else {
                    vis[a[i]] = 1;
                }
            }
        }
        maxn = max(maxn, res);
    }
    
    printf("%d", maxn);

    return 0;
}