题解 | #称砝码#

#include <stdio.h>
#include<string.h>

int main() {
    int n;
    scanf("%d\n", &n);
    int m[12] = {0};//输入数组放大一些一边测试
    for (int i = 1; i <= n; i++) {
        scanf("%d", &m[i]);
    }
    int num[12] = {0},k = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &num[i]);
        k = k+num[i]*m[i];
    }

    int dp[12][200000];//dp[砝码种类][总质量]
    for (int i = 0; i<=n; i++) {
        dp[i][0] = 1;//不放砝码算一种摆法
    }

    for (int i = 1; i<=n; i++) {
        for (int j = 1; j <= k; j++) {
            if (dp[i-1][j] == 1) {
                dp[i][j] = 1;//如果只有一种砝码的情况能摆出这个质量，那么再加一种也能摆出这个质量（加的那种不上称）
                continue;
            }
            for (int x = 1; x<=num[i]; x++) {
                if (j>=x*m[i]) {//判断能不能再加一个当前编号的砝码
                    if (dp[i-1][j-x*m[i]] == 1) {
                        dp[i][j] = 1;
                        break;
                    }
                }
            }
        }
    }

   
    int kinds=0;
    for(int i=0;i<=k;i++)
    {
        kinds+=dp[n][i]; //只遍历dp砝码数量为n的数组，加出值量种类数
    }
    printf("%d\n",kinds);
     
    return 0;
}