安徽省建设工程造价信息网站,要怎样建设网站,网页设计代码全过程,网站布局怎么写题目
就是一个英雄瞎搞之类为世界作出贡献#xff0c;蓝后某zz公司免费给他糖#xff0c;然后由于某些原因他只能拿能整除k数量糖果#xff0c;然后每个盒子里有一定数量的糖果#xff0c;拿了盒子就必须拿完里面所有的糖果#xff0c;求他怎么拿的最多。 输入
5 7 1 …题目
就是一个英雄瞎搞之类为世界作出贡献蓝后某zz公司免费给他糖然后由于某些原因他只能拿能整除k数量糖果然后每个盒子里有一定数量的糖果拿了盒子就必须拿完里面所有的糖果求他怎么拿的最多。 输入
5 7 1 2 3 4 5
输出
14
样例解释
Dzx的选择是234514这样糖果总数是7的倍数并且是总数最多的选择。 解题思路
emmmmmmmmmmmmmmmmmmmmmmm?其实我开始是用背包做的但是数据忒大了QAQ。所以…… 好吧讲正事 我们用f[i][j]表示前i个糖果数量%k余j时的最大值。蓝后我们就可以酱紫做。一个是选择这个糖一个是不选这个就是我不要这个了 ╯^╰ 。 动态转移方程 f[i][(f[i-1][j]a[i])%k]max(f[i][(f[i-1][j]a[i])%k],f[i-1][j]a[i]) 代码
#includecstdio
#includeiostream
using namespace std;
int n,k,a[10001],m;
int f[1001][1001];
int main()
{scanf(%d%d,n,k);for (int i1;in;i) {scanf(%d,a[i]);}//以上↑为输入for (int i1;in;i){for (int j0;jk;j) f[i][j]f[i-1][j];//全部初始化为这次不选糖for (int j0;jk;j)f[i][(f[i-1][j]a[i])%k]max(f[i][(f[i-1][j]a[i])%k],f[i-1][j]a[i]);//选择这个糖时求最优解。}printf(%d,f[n][0]);//输出
}
