首页 > 其他分享 >P1466 Subset Sum

P1466 Subset Sum

时间:2023-08-23 15:26:45浏览次数:59  
标签:Subset return int P1466 long sum Sum dp

对于从 1∼n 的连续整数集合,能划分成两个子集合,且保证每个集合的数字和是相等的
求可以划分的方案数

1. 动态规划

long long maxval(int n){ 
    int sum = (1+n)*n/2;
    if(sum%2==1) return 0;
    vector<long long> dp(sum+1)
    dp[0] = 1;//边界方案数为1
    for(int i=1;i<=n;i++)
        for(int j=sum;j>=i;j--)
            dp[j]+=dp[j-i];
    return dp[sum/2]/2;
}

标签:Subset,return,int,P1466,long,sum,Sum,dp
From: https://www.cnblogs.com/929code/p/17651710.html

相关文章

  • js 计算对象数组中某个字段sum之和
    1、一个字段之和要计算一个对象数组中某个字段的和,你可以使用JavaScript的Array.prototype.reduce()方法。reduce()方法对数组中的每个元素执行一个提供的函数,并将结果累积为单个值。以下是一个示例:假设你有一个对象数组 data,每个对象都有一个 value 字段,你想计算所有对......
  • leetcode-1-two sum(brute force, hash table)
    Wecanusebruteforcetogetit,usetwoforloopiandj,whichi=1:nandj=i:n.However,thetimecomplexityisO(n^2),whichisnotefficient.Usehashtable,thefirstthingisfirststoreeveryelementtotable,thendotraverseagaintolookup......
  • 20230619 java.util.IntSummaryStatistics
    介绍java.util.IntSummaryStatisticspublicclassIntSummaryStatisticsimplementsIntConsumer统计的指标:count,sum,min,average,maxAPI构造器IntSummaryStatistics()IntSummaryStatistics(longcount,intmin,intmax,longsum)publiccombinevoidcombi......
  • [ABC238E]Rcange Sums
    前言一道水得不能再水的题,虽说在图论的题单里,但我真的没有用图,用了并查集就轻松\(AC\)。大意输入\(q\)个\(l,r\),表示知道\(l\)到\(r\)的区间,最后问能不能知道\(0\)到\(n\),能就输出Yes,不能就输出No。思路图论做法:可以把知道\(l\)到\(r\)的区间抽象为从\(l-1\)向\(r\)连一条边......
  • [ABC098D] Xor Sum 2 题解
    题解传送门题目大意给出一个序列\(A\),求\(A_l\oplusA_{l+1}\oplus\dots\oplusA_r=A_l+A_{l+1}+\dots+A_r\)(\(\oplus\)即为\(xor\)异或)解析众所周知,异或是位运算中的一种不进位加法,即为如果两个\(bit\)相等返回\(0\),反之返回\(1\)。为什么说是不......
  • CF1762E Tree Sum 题解
    题意对于一棵\(n\)个节点的树\(T\),定义\(\operatorname{good}(T)\)为真当且仅当边权\(w\in\left\{-1,1\right\}\)且对于任意节点\(u\),均有\(\displaystylef(u)=\prod\limits_{\left(u,v\right)\inE}w\left(u,v\right)=-1\)。求\[\sum\limits_{\operat......
  • 使用MD5算法和sha512sum校验和检验文件完整性
    目录一.前言二.MD5算法简介三.什么是校验和四.使用MD5算法和sha512sum校验和检验文件完整性五.总结一.前言在我们日常生活中,无论是下载文件、传输数据还是备份重要信息,如何确保数据的完整性始终是一个不能忽视的问题。本文将向大家介绍如何使用MD5算法和sha512sum校验和来进行文......
  • [口胡记录] AGC020C Median Sum
    (题目传送门)一开始口胡结论,发现假了……把所有的子集和放到数轴上,惊奇地发现它们关于\(\dfrac{sum}{2}\)对称,于是做一遍存在性背包,从\(\dfrac{sum}{2}\)开始找第一个存在的子集和就好了因为\(n,a_i\leq2000\),需要\(\rmbitset\)优化#include<bits/stdc++.h>usingname......
  • [LeetCode][64]minimum-path-sum
    ContentGivenamxngridfilledwithnon-negativenumbers,findapathfromtoplefttobottomright,whichminimizesthesumofallnumbersalongitspath.Note:Youcanonlymoveeitherdownorrightatanypointintime. Example1:Input:grid=[[......
  • LeetCode[64]MinimumPathSum
    ContentGivenamxngridfilledwithnon-negativenumbers,findapathfromtoplefttobottomright,whichminimizesthesumofallnumbersalongitspath.Note:Youcanonlymoveeitherdownorrightatanypointintime. Example1:Input:grid=[[......