原题大意

给一个数列A，每次从里面取一个数，然后用已经取出的数之和去mod这个数，得到的值加入score里，并且把这个数加入到已经取出的集合里，直到取完所有数，问score最大是多少？

算法分析

本想贪心来写发现完全错了，看了题解才知道用dp，题中给出的n最大为20，所以很容易用位运算进行状态压缩，然后用记忆型dp来写，题解中给出了转移方程：
f(s) = max(f(subset(s,i))) + (∑ e) mod ai;
subset(s,i)，指除了ai以外包含s里所有元素的集合
这里的需要枚举i，e属于subset(s,i)。

转移方程详见题解：

https://www.hackerrank.com/contests/rookierank-3/challenges/max-score/editorial

程序代码

#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
int n;
ll a[25];
ll d[1<<21];

ll dp(ll s){
    ll &ans = d[s];
    if(ans != -1) return ans;
    ans = 0;
    if(s == 0) return ans;

    for(int i = 0; i < n; i++){
        ll t, sum;
        if((1<<i)&s){
            t = s ^ (1<<i);//t即为subset(s,i)
            sum = 0;
            for(int j = 0; j < n; j++){
                if((1<<j)&t){
                    sum+=a[n-1-j];
                }
            }
            sum %= a[n-1-i];
            ans = max(dp(t) + sum ,ans);
        }
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    mem(d,-1);
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    ll ans = 0;
    cout << dp((1<<n)-1)<<endl;
    return 0;
}