题解 P1490 买蛋糕

· · 题解

也许你可以打表看出来，也许不能，但别急，我们有看似靠谱一点的思维方法

看看样例：6

可行方案：

①1 2 3;

②1 2 4.

我们发现，对于方案①，组成3的时候有两种方法（1+2或3），而方案②只有一种。换而言之，3的利用是有浪费的。而不浪费的方案②还可以组成7。

那么，我们咋让她(每个数)都用好自己呢

很简单，百合就行了

联想一下二进制位下的数

可不是嘛，这个$2^i$的每个数利用率可高了 由此可知，**二进制的位数即为这个最小的正整数**。 ------------ 想明白第一问以后，应该给出了一个相对的第二问的思维导向。（当然不绝对哈） 当每个数的利用率最大的时候，她们能够凑成的最大整数即为她们的和，这点是毋庸置疑的。 那么，在利用率相对不是那么大的时候呢？ 我们注意到，此时已经有了一个限制条件：**已有的最小正整数** 手动模拟一下，确实是仍然成立的。（其实是不太会证啦） 这时候，我们就把参与量**已使用的各数之和**和**凑成的最大整数**搞到一起去了 考虑$dp[k]$代表凑成时$k$的方案数。看看这时候还要压哪些信息进去。 ~~显然~~，剩下的必要信息还有第$i$个数和第$i$个数的值$j **转移方程** $dp[i+1][l][k+l]+=dp[i][j][k];

其中l为枚举的下一个填充数

核心代码：

    dp[1][1][1]=1;
    for(int i=1;i<ans;i++)
        for(int j=i;j<=(1<<(i-1));j++)
            for(int k=i*(i-1)/2;k<(1<<i);k++)
                for(int l=j+1;l<=k+1;l++)
                    if(l+k<=n)
                        dp[i+1][l][k+l]+=dp[i][j][k];
                    else
                        dp[i+1][l][n]+=dp[i][j][k];

注意j,k,l的上下界，都是被已经得到的第一问给约束住了

当然，也没必要跑这么死，比如k从i开始反而会快一些。

至于if和else的判断，是为了方便求最后结果的一点点小贪心了。