刷题网址：https://csacademy.com/contest/archive/

Divisor Clique

\quad 一个简单的dp，首先将数组从小到大排序，假设dp[i[表示使用排好序的数组前i个数并且使用第i数的情况下能得到的最大子集，则$dp[i]=max(dp[j]+1),j\le i且a[i]\%a[j]=0$。程序如下：

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 2010;
int a[N], dp[N];

int main() {
    int n; cin >> n;
    for(int i = 0; i < n; i ++ ) cin >> a[i];
    sort(a, a + n);
    int res = 0;
    for(int i = 0; i < n; i ++ )
    {
        dp[i] = 1;
        for(int j = 0; j < i; j ++ )
            if(a[i] % a[j] == 0) 
                dp[i] = max(dp[i], dp[j] + 1);
        res = max(res, dp[i]);
    }
    cout << res << endl;
    return 0;
}

Max Even Subarray

#include <iostream>
using namespace std;

const int N = 100010;
int a[N];
struct P
{
    long long odd, even;
}dp[N];

int main() {
    int n; cin >> n;
    for(int i = 0; i < n; i ++ ) cin >> a[i];
    
    long long res = -1e18;
    for(int i = 0; i < n; i ++ ) dp[i].odd = a[i], dp[i].even = -1e16;
    for(int i = 1; i < n; i ++ )
    {
        long long t1 = dp[i - 1].odd + a[i], t2 = dp[i - 1].even + a[i];
        dp[i].even = max(dp[i].even, t1);
        dp[i].odd = max(dp[i].odd, t2);
        res = max(res, dp[i].even);
    }
    cout << res << endl;
    return 0;
}