【洛谷P1490】买蛋糕

佚名 6年前 (2019-05-08) 随笔 707人围观抢沙发百度已收录

题目大意：给定一个正整数 N，求至少从 [1,N] 中选出多少个数能够表示出 [1,N] 中的所有整数，每个数只能被选 1 次，并求出对于最优解有多少种不同的选择方案。

题解：好题。
仅考虑用最少的不同数字组合出 [1,N] 中所有的数，答案应该是 N 的二进制分解后的总位数，即：选出用 2 的幂次的数去组合是最好的方式。
若从 dp 的角度进行考虑，可以发现，对于从 [1,N] 中的数对答案来说都有选或不选两种情况，因此可以看成是背包问题的变种。
设 \(dp[i][j]\) 表示前 i 个数字中选出若干数，能够组合出 [1,j] 中所有数字的选出数字的最小个数。转移时的决策有两种，即：选 i 与不选 i，状态转移方程为
\[ dp[i][j]=min\{dp[i-1][j],dp[i-1][k]+1,k=max(i-1,j-i)\} \]
注意，这里对于 k 的取值不能仅仅是 j-i，若 \(j-i<i-1\)，则添加 \(i\) 后能够组合出的区间为 \([0,j-i]+[i,j]\)，发现中间部分断开了，不符合状态的要求，因此 \(j-i\) 取值的最小值是 \(i-1\)，即：\([0,i-1]+[i,j]\)。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn=1010;

int n,f[maxn][maxn],g[maxn][maxn];

void solve(){
    memset(f,0x3f,sizeof(f));
    g[0][0]=1,f[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=n;j++){
            int k=max(i-1,j-i);
            f[i][j]=min(f[i-1][j],f[i-1][k]+1);
            if(f[i][j]==f[i-1][j])g[i][j]+=g[i-1][j];
            if(f[i][j]==f[i-1][k]+1)g[i][j]+=g[i-1][k];
        }
    }
    printf("%d %d\n",f[n][n],g[n][n]);
}

int main(){
    scanf("%d",&n);
    solve();
    return 0;
}