【DP】CSL分苹果

红太狼 2024-03-24 10:23 31阅读 0赞

**典中典的DP啊**

**过了**

**我真牛逼**

[1020-CSL分苹果\_2021秋季算法入门班第七章习题：动态规划1 (nowcoder.com)][1020-CSL_2021_1 _nowcoder.com]

题意：

![590571419642499fb9e5779406dd74a2.png][]

思路：

典中典的DP状态设计：

设dp\[i\]\[j\]为前i个数能凑成j的方案数

然后就可以去考虑背包地DP了

最后怎么统计答案

就是遍历所有状态，取sum/2-j最小的方案输出就好了

Code：

#include <bits/stdc++.h>
    using namespace std;
    //#define int long long
    const int mxn=1e3+10;
    const int mxe=1e6+10;
    int n,sum=0;
    int a[mxn],dp[mxn][10010];
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=10000;j++){
                dp[i][j]+=dp[i-1][j];
                if(j>=a[i]) dp[i][j]+=dp[i-1][j-a[i]];
            }
        }
        int ansmi;
        double mi=100000000.0;
        for(int j=1;j<=10000;j++){
            if(dp[n][j]==0) continue;
            if(mi>abs(sum/2.0-j*1.0)){
                mi=abs(sum/2.0-j*1.0);
                ansmi=j;
            }
        }
        cout<<min(ansmi,sum-ansmi)<<" "<<max(ansmi,sum-ansmi)<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[1020-CSL_2021_1 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/24213/1020
[590571419642499fb9e5779406dd74a2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/4d2e6a6f8bfc4093a172b6e321254655.png

发表评论取消回复

表情：

评论列表（有 0 条评论，31人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法题】分苹果

![在这里插入图片描述][393a02eda50245589b33aa13bdebb478.png] package binary; import

骑猪看日落/ 2024年03月27日 12:00/ 0 赞/ 45 阅读

相关【DP】CSL分苹果

典中典的DP啊过了我真牛逼 [1020-CSL分苹果\_2021秋季算法入门班第七章习题：动态规划1 (nowcoder.com)][1020-CSL_2021_1

红太狼/ 2024年03月24日 10:23/ 0 赞/ 32 阅读

相关 python分苹果问题_给大家分享一个「Python算法题」分苹果

把num初值为 N-1之后，开始倒推，上一只熊取之前的苹果数为num = num + num/(N-1)+1，再判断这个数字能否被N-1整除，若可以，继续向前倒推，若不能，说明

水深无声/ 2023年01月09日 03:39/ 0 赞/ 237 阅读

相关 pku 1664 分苹果(整数划分)

\include <iostream> using namespace std; int f(int m, int n) \{ if(m < 0) return 0; if(m

偏执的太偏执、/ 2022年08月13日 00:50/ 0 赞/ 100 阅读

相关分苹果（C语言实现）

1、题目描述果园里有堆苹果，N（1＜N＜9）只熊来分。第一只熊把这堆苹果平均分为N份，多了一个，它把多的一个扔了，拿走了一份。第二只熊把剩下的苹果又平均分成N份，又多了

本是古典何须时尚/ 2022年06月08日 09:21/ 0 赞/ 213 阅读

相关 c语言实例--巧分苹果

问题：一家农户以果园为生，一天，父亲推出一车苹果，共2520个，准备分给他的6个儿子。父亲按事先写在一张纸上的数字把这堆苹果分完，每个人分到的苹果个数都不相同。他说：“老大，把

傷城~/ 2022年05月24日 02:54/ 0 赞/ 170 阅读

相关编程题：分苹果

题目描述 n 只奶牛坐在一排，每个奶牛拥有 a i 个苹果，现在你要在它们之间转移苹果，使得最后所有奶牛拥有的苹果数都相同，每一次，你只能从一只奶牛身上拿走恰好两个苹果

小鱼儿/ 2022年05月23日 02:08/ 0 赞/ 221 阅读

相关猴子分苹果

题目：秋天到了，n只猴子采摘了一大堆苹果放到山洞里，约定第二天平分。这些猴子很崇拜猴王孙悟空，所以都想给他留一些苹果。第一只猴子悄悄来到山洞，把苹果平均分成n份，把剩下的m个苹

绝地灬酷狼/ 2022年04月10日 02:27/ 0 赞/ 213 阅读

相关猴子分苹果-Java

问题描述秋天到了，n只猴子采摘了一大堆苹果放到山洞里，约定第二天平分。这些猴子很崇拜猴王孙悟空，所以都想给他留一些苹果。第一只猴子悄悄来到山洞，把苹果平均分成n份

秒速五厘米/ 2022年03月20日 14:27/ 0 赞/ 199 阅读

相关每天一题(7)-分苹果

每天一题-分苹果题目代码题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_sha

曾经终败给现在/ 2021年11月08日 18:48/ 0 赞/ 312 阅读