题解

31 条题解

  • 5
    @ 2016-11-14 16:23:52

    问题的数学模型是从前n个数字中选取尽可能少的个数,使得其和取遍1..m中所有的值。不难想到用dp[i][j]表示前i个数字选择取遍1..j的尽可能少的个数。有

    dp[0][0] = 0
    dp[i][j] = min{dp[i-1][j], dp[i-1][k]+1 | k >= i+1, 且j-i <= k < j}

    由于不等式i < j <--> dp[a][i] <= dp[a][j]显然成立,所以dp[i-1][k]取最小值必然在k = max{i+1, j-i}。也不难证明这种方法既不重复又不遗漏,因此用数组cnt根据决策统计即可。

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    
    int dp[1005][1005];
    int cnt[1005][1005];
    int main()
    {
        int n;
        cin >> n;
        memset(dp, 127/3, sizeof dp);
        memset(cnt, 0, sizeof cnt);
        dp[0][0] = 0;
        cnt[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                //if (j <= i) continue;
                dp[i][j] = dp[i-1][j];
                int k = max(i-1, j-i);
                dp[i][j] = min(dp[i][j], dp[i-1][k]+1);
                if (dp[i][j] == dp[i-1][j])
                    cnt[i][j] += cnt[i-1][j];
                if (dp[i][j] == dp[i-1][k]+1)
                    cnt[i][j] += cnt[i-1][k];
            }
        }
        cout << dp[n][n] << " " << cnt[n][n] << endl;
        return 0;
    }
    
  • 3
    @ 2017-05-08 12:27:35
    /*
    首先有这么一个结论:对任意n:1,2,4,8,......总是一个最优方案.
    那么很容易知道 最少个数为log2n+1
    假设第k-1个数是a[k-1],前k-1个数能达成的最大的连续的数是sum,
    那么第k个数的范围一定是a[k-1]+1到sum+1.
    然后用动态规划来求解方案总数
    用f[count,last,max]
    表示count个数、最后的数(也是最大的)为last、能组成1到max中所有正整数的方案数
    然后状态转移方程就很容易出来了
    仔细看代码叭~好晚了要睡觉咯~233333
    注意到n最大1000
    所以ans最大为10
    所以第一维开到11   二三维最大就是1000咯
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    using namespace std;
    
    const int maxn=1005;
    int n;
    int ans;
    int tot;
    int f[11][maxn][maxn];
    
    int main()
    {
        cin>>n;
        ans=(int)log2(n)+1;
        f[1][1][1]=1;
        for(int i=1;i<ans;i++)
            for(int j=i;j<=(1<<(i-1));j++)
                for(int k=i;k<=((1<<i)-1);k++)
                    if(f[i][j][k])
                        for(int p=j+1;p<=k+1;p++)
                        {
                            if(p+k<=n)//如果加起来在范围内
                                f[i+1][p][k+p]+=f[i][j][k];
                            else//加起来不在范围内
                                f[i+1][p][n]+=f[i][j][k];
                        }
        for(int i=1;i<=n;i++)
            tot+=f[ans][i][n];
        cout<<ans<<" "<<tot<<endl;
        return 0;
    }
    
    
  • 0
    @ 2020-11-07 11:39:59
    /*
        这里不是采用动态规划,用dfs + 剪枝, 注意提前一个节点剪枝, 参考了博客:
        https://blog.csdn.net/a_bright_ch/article/details/83786942
        这里的解释很详细
    */
    
    #include <algorithm>
    #include <cmath>
    #include <iostream>
    #include <string>
    using namespace std;
    const int maxn = 1002;
    
    int len, ans, n;
    
    void dfs(int k, int maxx, int sum) {
        // k为dfs树层数, maxx为最大的是(最后的数, 当前数), sum为和
    
        // 若不前剪枝, 会超时
        // if (k == len) {
        //     if (n <= sum) ans++;
        //     return;
        // }
    
        if (k == len) {
            // ans += (sum * 2 + 1) - (n - 1);
            int num = sum - maxx + 1;  //下一节点的孩子数
    
            //下面给出下一节点的sum的范围
            // sum + maxx + 1 <= newsum <= 2 * sum + 1;
    
            if (n <= 2 * sum + 1) {  // n <= newsum
                if (n <= sum + maxx + 1)
                    ans += num; //sum - maxx + 1
                else
                    ans += num - (n - sum - maxx - 1);  //2 * sum + n - 2
            }
            return;
        }
        for (int i = maxx + 1; i <= sum + 1; i++) dfs(k + 1, i, sum + i);
    }
    
    int main() {
        cin >> n;
        len = (int)log2(n) + 1;
    
        dfs(1, 0, 0);  // maxx, sum都是上一节点的值
        cout << len << " " << ans << endl;
        system("pause");
        return 0;
    }
    
    
  • 0
    @ 2018-05-02 23:27:00

    #include <bits/stdc++.h>

    using namespace std;

    int n;
    int f[1010][1010];
    int cnt[1010][1010];

    int main()
    {
    cin >> n;
    int ans = 1,count = 2;
    while(count <= n){
    ans++;
    count *= 2;
    }
    cout << ans << " ";
    ////////////////////////////////////////////////
    memset(f,0,sizeof(f));
    memset(cnt,0,sizeof(cnt));
    f[0][0] = 0;
    cnt[0][0] = 1;

    for(int i = 1; i <= n; i++){
    for(int j = 0; j <= n; j++){
    int help = max(i-1,j-i);
    if(f[i-1][j] <= f[i-1][help]+1){
    f[i][j] = f[i-1][j];
    cnt[i][j] += cnt[i-1][j];
    }
    else{
    f[i][j] = f[i-1][help]+1;
    cnt[i][j] += cnt[i-1][help];
    }
    }
    }

    cout << cnt[n][n];
    return 0;
    }
    这....为啥是错的啊

  • 0
    @ 2009-11-09 21:35:57

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    - -! 动规......

  • 0
    @ 2009-09-26 10:01:06

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    第一次只加了数学方法的节支(有点写萎了)

    没有用倒数第二步时直接计算答案的方法有一个点1400+ms

    然后把数学方法改好又加上倒数第二步时直接计算答案就秒杀了= =

    另外要小心1的情况

    强烈建议加入512这个点><

    答案是10 1869956813

  • 0
    @ 2009-09-13 13:43:09

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 322ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 431ms

    ├ 测试数据 07:答案正确... 775ms

    ├ 测试数据 08:答案正确... 9ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

  • 0
    @ 2009-06-29 13:34:45

    对于n=128,动规出的结果是8 435939。

    oimaster的程序只要将k:=trunc(ln(n)/ln(2))+1;改为k:=trunc(ln(n)/ln(2)+1e-8)+1;就行了。

    这种方法最保险:

    i:=1;k:=0;

    while i

  • 0
    @ 2009-06-15 18:15:34

    oimaster 所谓的秒杀程序有错

    输入: 128

    输出:7 0

    不可能是0吧.....

    我的是 435939

    curimit 的是 436003

    不知道哪个对

    建议测试数据应加上 128

  • 0
    @ 2009-03-28 19:59:09

    这道题很明显是DP呀,怎么划到搜索下了

  • 0
    @ 2009-03-23 19:25:02

    用了CJF神牛的数学剪枝

    看来写烂了..最大的点要1s+

  • 0
    @ 2009-03-18 16:15:22

    还是搜

  • 0
    @ 2009-02-14 01:54:04

    搜索在最后一步时直接计算出答案可以秒杀。

    增加的种数=max-min+1

    但是精益求精,在搜索倒数第二步时也可以直接计算出答案。

    增加的种数是一个非常复杂的分段函数。真是太复杂了,算了好长时间。

    下面是搜索到倒数第二步时直接计算答案的程序。

    program dangao;

    var

    n,m,tot:longint;

    ans:int64;

    procedure search(lev,last:longint);

    var i,e,x,y:longint;

    begin

    if tot>=n then e:=n else e:=tot+1;

    if lev=m-1 then

    begin

    x:=last+1; if xtot+1 then y:=tot+1;

    if xtot+1 then y:=tot+1;

    if x

  • 0
    @ 2009-02-05 19:41:20

    秒杀的程序:

    program Vijos_P1154;

    var

    f:array[1..10,1..1000,1..1000] of longint;

    n,k,count,last,max,i,total:longint;

    begin

    readln(n);

    k:=trunc(ln(n)/ln(2))+1;

    fillchar(f,sizeof(f),0);

    f[1,1,1]:=1;

    for count:=1 to k-1 do

    for last:=count to 1 shl (count-1) do

    for max:=count to 1 shl count-1 do

    if f[count,last,max]>0 then

    for i:=last+1 to max+1 do

    if max+i

  • 0
    @ 2008-11-02 20:43:54

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 166ms

    ├ 测试数据 07:答案正确... 166ms

    ├ 测试数据 08:答案正确... 150ms

    ├ 测试数据 09:答案正确... 166ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:648ms

    原来题解是在搜完倒数第二个的时候手工判断最后一个能取什么值....

    加上这个就能A了,不过还是不够快~

  • 0
    @ 2008-10-22 09:11:16

    狂晕 这题搜索过不了丫...

    怎么是dp...

    program mzn;

    var j,t,n,pre,last,max,i,k:longint;

    a:array[1..10]of integer;

    f:array[1..10,1..1000,1..1000]of longint;

    total:longint;

    begin

    readln(n);

    k:=trunc(ln(n)/ln(2))+1; write(k,' ');

    for i:=1 to k do

    a[i]:=1 shl (i-1);

    f[1,1,1]:=1;

    for pre:=1 to k-1 do

    for last:=pre to a[pre] do

    for max:=1 to n do

    begin

    if f[pre,last,max]>0 then

    begin

    for i:=last+1 to max+1 do

    begin

    if max+i

  • 0
    @ 2008-09-30 16:05:19

    最近比较傻..上来居然用DFS+背包,无限TLE....去掉背包并加上两个剪枝,0ms....

    假设第k-1个数是a[k-1],前k-1个数能达成的最大的连续的数是sum,那么第k个数的范围一定是a[k-1]+1到sum+1.

  • 0
    @ 2008-09-24 15:38:45

    我傻了

    首先有这么一个结论:对任意n:1,2,4,8,......总是一个最优方案

    然后有这么一个加强版的结论:

    若现在已搜了k个数覆盖了1..s,那么剩下的数为s+1,2*(s+1),4*(s+1),.......一定是最优方案

    然后就可以利用这个剪枝了.......

  • 0
    @ 2008-09-17 12:31:45

    我邪恶了= =

    N^4DP加表= =

  • 0
    @ 2008-08-10 15:02:35

    可以用DP做,主要是把数范围的上下界尽量弄准确,减少多余的计算,这样都是0ms

信息

ID
1154
难度
4
分类
其他 | 数学动态规划 点击显示
标签
递交数
532
已通过
215
通过率
40%
被复制
5
上传者