蓝桥杯2021年第十二届省赛真题-砝码称重(DP)

动态规划问题：

bool类型DP数组代表对于前i个砝码是否可以称出重量j（默认左盘放待称物体）

有三种情况：

1. 不加第i个砝码也能称出来 dp[i-1][j]

2. 加在右盘 dp[i-1][j+arr[i]]

3. j加载左盘 dp[i-1][abs(j-arr[i])]

三种情况只要有一种为真既可

#include<iostream>

#include<cmath>

using namespace std;

const int N=110,M=2e5+10;

bool dp[N][M];

int arr[N];

int n,m;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++){

        cin>>arr[i];

        m+=arr[i];

    }

    dp[0][0]=1;

    for(int i=1;i<=n;i++){

        for(int j=0;j<=m;j++){

            dp[i][j]=dp[i-1][j]||dp[i-1][j+arr[i]]||dp[i-1][abs(j-arr[i])];

        }

    }

    int ans=0;

    for(int i=1;i<=m;i++){

        if(dp[n][i]) ans++;

    }

    cout<<ans<<endl;

    return 0;

}