P2663 越越的组队 思维01背包

网友投稿 639 2022-11-22

P2663 越越的组队 思维01背包

P2663 越越的组队 思维01背包

​​传送门​​ 思路：一开始怎么也想不出来如何处理接近sum/2的情况。后来看了题解才知道，可以把总的分数的一半看作一个背包，而将每个分数看成它的价值。dp[i]表示在分数为i的情况下，最多能装多少分数。在背包中维护一个最大值即可。

/*** From:* Qingdao Agricultural University* Created by XiangwangAcmer* Date : 2019-10-16-19.59.14* Talk is cheap.Show me your code.*/#include#include#include#include#include#include#include#include#include#include#include#include#define ll long longusing namespace std;const ll maxn = 1e6 + 5;const ll minn = 1e9 + 5;const ll mod = 1000000007;const int INF = 0x3f3f3f3f;const long long LIMIT = 4294967295LL;vectorv[maxn];int dp[maxn];vectorG[maxn];bool row[maxn], col[maxn];bool flag = 0;queueq;int a[maxn];int main() { ios::sync_with_stdio(false); int n; cin >> n; int sum = 0; int ans=0; for(int i = 1; i <= n; i++) cin >> a[i], sum += a[i]; for(int i = 1; i <= n; i++) for(int j = sum / 2; j >= a[i]; j--) { dp[j] = max(dp[j], dp[j - a[i]] + a[i]); ans = max(ans,dp[j]); } cout << ans << endl; return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：思维
上一篇:2019icpc沈阳区域赛 A + H题
下一篇:Android 10 根文件系统和编译系统(一)：根文件系统目录结构
相关文章

 发表评论

暂时没有评论，来抢沙发吧~