UOJ66 新年的巧克力棒 题解

题目链接：#66. 新年的巧克力棒

题意：马上就要到羊年了，羊村一片欢腾，懒羊羊则懒洋洋地躺在草坪上吃新年的巧克力棒。

他手上的巧克力棒是个由 \(n\) 个巧克力单元格组成的长度为 \(n\) 的长条，现在懒羊羊想把巧克力棒掰开成一个个小单元格。

初始时懒羊羊会把这根巧克力棒丢在草坪上，然后每次懒羊羊会从草坪上拿起一根长度大于 \(1\) 的巧克力棒，然后从某两个相邻的单元格的间隙处掰开变成两根巧克力棒，然后把这两根巧克力棒丢在草坪上。懒羊羊初始愉悦值为 \(0\)，每次掰开巧克力棒后如果这两根巧克力棒长度相等，那么懒羊羊将提升 \(1\) 点愉悦值。

当然，草坪上全是长度为 \(1\) 的巧克力棒时懒羊羊就会停止操作。现在懒羊羊想知道，他能获得的愉悦值最多是多少？

设 \(f_i\) 表示长度为 \(i\) 的巧(áo)克(lì)力(gèi)能获得的最大价值，则 \[ f_i = \max\limits_{1 \le j < i}\left\{f_j + f_{i-j} + [j=i-j]\right\} \] 然后这东西是 \(O(n^2)\) 的，看上去也没什么能优化的

注意到有 \(n \le 10^3\) 的部分分，说明我们推的柿子是大概率正确的

好像没什么思路，但是这个 \(n\le 10^9\) 印发了我们的好奇心（确信

然后打打表试试，打表代码如下：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1005)

int f[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    for(int i=2; i<=100; i++)
        for(int j=1; j<i; j++)
            f[i]=max(f[i],f[j]+f[i-j]+(j==i-j));
    for(int i=1; i<=20; i++)
        cout << i << " " << f[i] << '\n';
    return 0;
}

表：

1 0
2 1
3 1
4 3
5 3
6 4
7 4
8 7
9 7
10 8
11 8
12 10
13 10
14 11
15 11
16 15
17 15
18 16
19 16
20 18

观察到 \(1,2,4,8\) 都减了 \(1\) ，而 \(6,10\) 减了 \(2\)

前面这个又是 \(2\) 的次幂，难道是？？

答案确实是 \(n - \text{popc}(n)\) ，这里的 \(\text{popc}(n)\) 表示 \(n\) 在二进制下的 \(1\) 的个数

于是超短码就出现啦：

#include <cstdio>
signed main()
{
    int x,y; 
    for(scanf("%d",&x); x--;)
        scanf("%d",&y),printf("%d\n",y-__builtin_popcount(y));
    return 0;
}

至于为什么答案是这个，可以看看这里的证明 link