| 题目名称 | 618. [金陵中学2007] 最优分解方案 |
|---|---|
| 输入输出 | best.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2011-11-11加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 查看题解 | 分享题解 |
| 通过：52， 提交：140， 通过率：37.14% | ||||
 op_组撒头屯 |
100 | 0.000 s | 0.00 MiB | C++ |
|
Lfc_HeSn |
100 | 0.000 s | 0.00 MiB | C++ |
|
该账号已注销 |
100 | 0.000 s | 0.00 MiB | C++ |
|
ムラサメ |
100 | 0.000 s | 0.00 MiB | C++ |
 Ezoi_XY |
100 | 0.001 s | 0.17 MiB | Pascal |
 lizhe |
100 | 0.002 s | 0.12 MiB | Pascal |
 钨铅 |
100 | 0.002 s | 0.15 MiB | Pascal |
 ahmasoi |
100 | 0.002 s | 0.17 MiB | Pascal |
 Loist. |
100 | 0.002 s | 0.17 MiB | Pascal |
 苏轼 |
100 | 0.002 s | 0.17 MiB | Pascal |
| 本题关联比赛 | |||
| 20111111 | |||
| 20111111 | |||
| 关于 最优分解方案 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
发现了一个巨简便的算法，跟01背包很像，但是枚举方式需要改一下，推导的过程可以看我的博客
| ||||
|
| ||||
|
sbwxc
| ||||
|
找闺女找闺女
 | ||||
|
刚学会高精的时候很逗的看错了题，写了个一坨2×一坨3的玩意，蛤蛤
@raywzy 这个算法的证明其实是一道数论题 | ||||
|
这道题需要用高精度乘法（背代码狗撸过）.....然后就是主要的算法思想：将这个数分成以2为首项公差为1的等差数列，最后肯定会有一个余数然后从后往前将这个数均匀的撒在前几个数中（即+1），若分完一遍发现余数不为0则继续从后往前撒，然后相乘就好了，（这种题谁能想得出来啊喂QAQ.....）....最DT的是第一次交的时候发现c数组初始化不为0.....我明明开的是局部变量啊魂淡TAT....
| ||||
|
动规+高精度乘法搞定
f[i]表示i分解后得到的最大乘积 需用一个二位的bool型数组标记每一个数在每种情况下是否用过 | ||||
乌龙猹
cstdio
raywzy
Truth.Cirno【问题描述】
经过第一轮的游戏，不少同学将会获得圣诞特别礼物，但这时细心的数学课代表发现了一个问题：留下来的人太多而使礼物数量可能不够，为此，加试了一道数学题：将一个正整数 $n$ 分解成若干个互不相等的正整数的和，使得这些数的乘积最大，当主持人报出一个 $n$ 后，请你立即将这个最大值报出来，现请你帮你的好友编一个程序来解决这个问题。
【输入文件】
输入文件中只有 $1$ 个数 $n$ （其中 $1\leq n\leq 1000$ ）。
【输出文件】
输出文件中也是一个数，是乘积的最大值。
【输入样例】
7
【输出样例】
12