洛谷 P2347 砝码称重

嗯...

 

题目链接：https://www.luogu.org/problemnew/show/P2347

 

这道题——暴力枚举外加点DP的意思？

　　1.枚举每一种质量的砝码

　　2.枚举当前质量

　　3.如果没有被称出来过则打上标记

然后扫一遍，数一下打上标记的个数即可..注意初始化！！

 

AC代码：

#include<cstdio>
#include<iostream>

using namespace std;

int a[10], w[10] = {0, 1, 2, 3, 5, 10, 20};
int dp[10005], ans;

int main(){
    for(int i = 1; i <= 6; i++)    
        scanf("%d", &a[i]);
    dp[0] = 1;
    for(int i = 1; i <= 6; i++){
        for(int j = 1; j <= a[i]; j++){
            for(int k = 1000; k >= 0; k--){
                if(dp[k] && k + w[i] <= 1000){
                    dp[k + w[i]] = 1;//打标记 
                }
            }
        }
    }
    for(int i = 1; i <= 1000; i++){
        if(dp[i]) ans++;
    }
    printf("Total=%d", ans);
    return 0;
}