蓝桥杯官网 试题 PREV-265 历届真题 砝码称重【第十二届】【省赛】【研究生组】【C++】【C】【Java】【Python】四种解法

#include <bits/stdc++.h>
using namespace std;
const long long inf = 0x7fffffffffffffff;
bool dp[106][100006];
int a[106];
int main()
{
    int i,j,n,sum = 0; cin>>n;
   for(i = 1;i <= n;i++){
      cin>>a[i];
      sum+= a[i];
   }

   for(i = 1;i <= n;i++){
       for(j = 1;j <= sum;j++){
           dp[i][j] = dp[i-1][j];
           if(!dp[i][j]){
               if(j == a[i]) dp[i][j] = 1; 
                //判定的值与当前选择的砝码相等
               if(dp[i-1][j + a[i]])  dp[i][j] = 1;
      //检查当前i砝码与上一个状态（之前组合出的值）放在不同侧，是否可以组成j。
               if(dp[i-1][abs(j-a[i])]) dp[i][j] = 1;
      //检查当前i砝码与上一个状态（之前组合出的值）放在同一侧，是否可以组成j。
           }
       }
   }

   long long ans = 0;
    for(j = 1;j <= sum;j++) if(dp[n][j]) ans++;
    cout<<ans;
    return 0;
}

#include <stdio.h>
#include <stdlib.h>

enum
{
   ZDZZL = 100000 ,
   KY = 1 ,
   BX = 0 ,
} ;
void shuru(int,int []);
int qiu_zhongshu(int,int []);
int qiu_he(int,int []);
void jia( int , int [] , int ) ;
void bingru(int , int [],int []); 
int qiu_kys(int , int []);

void t_keyi(int n, int a[])
{
   while ( n -- > 0 )
   {
      printf("%d ",* a ++ ) ;
   }   
   putchar('\n');
}

int main(void)
{
   int n;
   scanf("%d",&n);
   int fama[n] ;
   shuru(n,fama);
   printf("%d\n",qiu_zhongshu(n,fama));
	return 0 ;
} 

int qiu_kys(int n, int ky[])
{
   int kys = 0 ;
   while ( n -- > 0 )
   {
      kys += * ky ++ ;
   }
   return kys ;
}

void bingru(int n, int y[],int x[])
{
   while ( n -- > 0 )
   {
      * y = * y || * x ;
      y ++ ;
      x ++ ;
   }
}

/*
3
6
  K K K    K K K  K K  K
K K K K K K K K B K K  K　元素值表示是否可以 
0 1 2 3 4 5 6 7 8 9 10 11 　用下标表示重量    
*/
void jia( int gs , int ky[] , int fmz )
{
   int zj[1+ZDZZL] = { BX } ; //记录可以增加的重量 
   int zl ;//用下标表示重量
   for ( zl = 0 ; zl < gs ; zl ++ )
   {
      if ( zl[ky] == KY ) 
      {
         zj[zl + fmz] = KY ;
         zj[abs(zl - fmz)] = KY ;
      }
   }
   bingru(gs,ky,zj); 
}

int qiu_he(int n,int a[])
{
   int he = 0 ;
   while ( n -- > 0 )
   {
      he += * a ++ ;
   }
   return he ;   
}

int qiu_zhongshu(int n,int fm[])
{
   int keyi[1+ZDZZL] = { KY } ; 
   int zzl = qiu_he(n,fm) ;
   while ( n -- > 0 )
   {
      jia( zzl + 1 , keyi , *fm ++) ;
   }
   return qiu_kys(zzl , keyi + 1);
}

void shuru(int n,int f[])
{
   while ( n -- > 0 )
   {
      scanf("%d",f ++ );
   }
}

import java.io.*;

public class Main {
    static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
    static int N=105;
    static int[] a=new int[N];
    static int[] b=new int[N];
    static int n,m=0;
    static boolean[][] f=new boolean[105][100010];
    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(bf.readLine().trim());
        String[] temp = bf.readLine().trim().split(" ");
        f[0][0]=true;
        b[0]=0;
        for (int i = 1; i <= n; i++){
            a[i] = Integer.parseInt(temp[i - 1]);
            b[i]=b[i-1]+a[i];
        }
        for (int i = 1; i <=n ; i++) {
            for (int j=0;j<=b[i];j++){
                f[i][j]=f[i-1][j] || f[i-1][Math.abs(j-a[i])] || f[i-1][j+a[i]];
            }
        }
        int cnt=0;

        for (int i=1;i<=b[n];i++){
            if (f[n][i]){
                cnt++;
            }
        }
        System.out.println(cnt);
    }

}

def res(num, se):
    N = len(se)
    s = set()
    if N == 0:
        se.add(num)
        return 1
    for set_ in se:
        s.add(abs(set_-num))
        s.add(abs(set_+num))
    se.add(num)
    for i in s:
        se.add(i)
    return len(se)

if __name__ == '__main__':

    n = int(input())
    nums = list(map(int, input().split()))
    nums.sort()
    se = set()
    dp = [0 for x in range(0, 100)]
    for i in range(n):
        dp[i] = res(nums[i],se)

    if 0 in se:
        dp[n - 1] = dp[n-1] - 1
    print(dp[n-1], end='')