[蓝桥杯2021省AB]砝码称重题目描述你有一架天平和NNN个砝码,这NNN个砝码重量依次是W1,W2,⋯ ,WNW_{1},W_{2},\cdots,W_{N}W1​,W2​,⋯,WN​。请你计算一共可以称出多少种不同的重量?注意砝码可以放在天平两边。输入格式输入的第一行包含一个整数NNN。第二行包含NNN个整数:W1,W2,W3,⋯ ,WNW_{1},W_{2},W_{3},\cdots,W_{N}W1​,W2​,W3​,⋯,WN​。输出格式输出一个整数代表答案。样例#1样例输入#13146样例输出#110提示【样例说明】能称出的10种重量是:1、2、3、4、5、6、7、9、10、111、

P8742[蓝桥杯2021省AB]砝码称重题解显然DPDPDP，考虑如何进行DPDPDP设状态转移数组fi,jf_{i,j}fi,j​表示在前iii个砝码中，有没有组成重量为jjj的方案。考虑转移情况，每个状态可以由：第iii个选了砝码iii在异侧第iii个选了砝码iii在同侧未选砝码iii转移而来则转移方程式为fi,j=fi−1,j−w[i]∣fi−1,j+w[i]∣fi−1,jf_{i,j}=f_{i-1,j-w[i]}\midf_{i-1,j+w[i]}\midf_{i-1,j}fi,j​=fi−1,j−w[i]​∣fi−1,j+w[i]​∣fi−1,j​由于可能会出现jjj在运算过程中

简单版（P2347）传送门原题传送门有一道类似的题目（P2347），先扯一扯~1.P2347题目分析动态规划入门题（01背包可行性问题）~我们设\(dp_j\)为能否用砝码称出\(j\)重量，1为可以，0为不可以。为了转移，\(dp_{_{0}}\gets1\)，什么都不放时，重量为0，因此可以称出。那么枚举\(dp_{_{1}}\simdp_{sum}(sum\)为砝码可称出的最大重量\()\)。如果\(j-w\)可以称出，且重量为\(w\)的砝码存在、未超出个数限制，则\(j\)可以称出。即\(dp_j=dp_{j-w}(j-w\geqslant0)\)那么动态转移方程显而易见：\(dp_