HJ151 模意义下最大子序列和（Easy Version）

• 题目
• 题解(13)
• 讨论(7)
• 排行

中等 通过率：38.55% 时间限制：1秒 空间限制：256M

知识点dfs

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

给定一个含有 nn 个正整数的数组 aa 以及一个正整数模数 mm。你可以任选若干下标递增的元素构成一个子序列（允许选择空序列）。设所选元素之和为 SS，求 S mod mSmodm 的最大可能值。

输入描述：

第一行输入两个整数 n,m (1≦n≦15, 1≦m≦109)n,m (1≦n≦15,1≦m≦109)。
第二行输入 nn 个整数 ai (1≦ai≦109)ai​ (1≦ai​≦109)。

输出描述：

输出一个整数，表示 S mod mSmodm 的最大值。

示例1

输入：

1 1 1

复制输出：

0

复制说明：

可选子序列有 ∅∅（空序列）和 (1)(1)，其元素和分别为 00、11；取模 m=1m=1 后结果均为 00，因此答案为 00。

#include<iostream> #include<vector> using namespace std; vector<int> nums; long long a[20]; long long res=0; int n,m; void dfs(int index){ long long ans=0; if(index==n){ for(int i=0;i<nums.size();i++){ ans=(ans%m+nums[i]%m)%m; } res=max(ans,res); return; } nums.push_back(a[index]); dfs(index+1); nums.pop_back(); dfs(index+1); } int main(){ cin>>n>>m; for(int i=0;i<n;i++){ cin>>a[i]; } dfs(0); cout<<res; return 0; }