阿里笔试 4.24 求指导
题意：给定一个n个元素的数组和m，从数组中挑选一个子序列，子序列的和对m取余最大，输出这个最大的余数。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
long m;
cin >> n;
cin >> m;
vector<long> vec(n);
long sum = 0;
for(int i = 0; i < n; i++) {
cin >> vec[i];
vec[i] = vec[i] % m; //数组存求余后的值
sum += vec[i];
}
if(sum < m) {
cout << sum;
return 0;
}
vector<long> dp(n); //dp[i]的意思是以数组i结尾的子序列的最大余数
dp[0] = vec[0];
for(int i = 1; i < n; i++) {
dp[i] = dp[i - 1]; //不拿
for(int j = 1; j <= i; j++) {
dp[i] = max(dp[i], (vec[i]+dp[i-j]) % m);//拿
}
}
cout << dp[n - 1];
return 0;
} 自测的样例没问题
输入：
6 11
4 12 3 7 6 2
输出：
10
6 11
4 12 3 7 6 2
输出：
10
求指点！
巨人网络公司福利 91人发布
