一维dp,一个砝码拆成一正一反两个砝码

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>//一维dp,思路是

//把每个砝码拆成一正一反两个质量，这样所有砝码都只需要放左边就行了。

using namespace std;

#define maxw 100010

#define maxn 110

int n;

int sum=0;

int a[maxn<<1];

int dp[maxw];

void init(){

    memset(a,0,sizeof(a));

}

void debug(){

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

        printf("%d ",dp[i]);

    }putchar('\n');

}

int main(){

    init();

    scanf("%d",&n);

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

        scanf("%d",&a[i]);

        sum+=a[i];

    }

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

        a[i]=-a[i-n];

    }

    dp[0]=1;

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

        for(int j=sum;j>=0;j--){

            if(dp[j]==1&&j+a[i]>0){

                dp[j+a[i]]=1;

            }

        }

        //debug();

    }

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

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

            if(dp[j]==1&&j+a[i]>0){

                dp[j+a[i]]=1;

            }

        }

        //debug();

    }

    //debug();

    int ans=0;

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

        if(dp[i])ans++;

    }

    printf("%d",ans);

    return 0;

}