分成一堆2和最多一个3
by pig1121 @ 2023-12-20 12:32:06
分出1肯定不划算。如果有数 $a$ 大于3,那么拆成 $(a-2)$ 和一个 $2$ 显然更优,如果有 $2$ 个以上的 $3$ ,那么把两个 $3$ 变成三个 $2$ 更优,所以只能除了最多一个 $3$ 之外全是 $2$ 。
by pig1121 @ 2023-12-20 12:39:11
分成一堆 $3$ 和最多两个 $2$。
如果 $n\bmod 3=0$,那么是 $n/3$ 个 $3$;
如果 $n\bmod 3=1$,那么是 $\lfloor n/3\rfloor-1$ 个 $3$,加上两个 $2$;
如果 $n\mod 3=2$,那么是 $\lfloor n/3\rfloor$ 个 $3$,加上一个 $2$。
```cpp
#include<cmath>
#include<cstdio>
#include<algorithm>
long double f[1001];
long double g(int n)
{
switch(n%3)
{
case 0:return powl(3,n/3);
case 1:return powl(3,n/3-1)*4;
case 2:return powl(3,n/3)*2;
}
return -1;
}
int main()
{
int n=1000;
for(int i=1;i<=n;i++)
{
for(int j=0;j<i;j++)
f[i]=std::max(f[i],f[j]+logl(i-j));
printf("%d %.15Lf %.15Lf\n",i,(expl(f[i])-g(i))/expl(f[i]),(expl(f[i])-g(i))/g(i));
//对比两者相对误差
}
return 0;
}
```
by Terrible @ 2023-12-20 12:50:01
@[pig1121](/user/924621) ?两个 $3$ 明显比三个 $2$ 更优啊
by Shxt_Plus @ 2023-12-20 12:52:12
@[Shxt_Plus](/user/249447) 写错了,是要3尽可能多
by pig1121 @ 2023-12-20 13:19:35