Smiling & Weeping
----不讨好所有冷漠 不辜负所有热爱
# [NOIP1996 提高组] 砝码称重
## 题目描述
设有 $1\mathrm{g}$、$2\mathrm{g}$、$3\mathrm{g}$、$5\mathrm{g}$、$10\mathrm{g}$、$20\mathrm{g}$ 的砝码各若干枚(其总重$ \le 1000$),可以表示成多少种重量?
## 输入格式
输入方式:$a_1 , a_2 ,a_3 , a_4 , a_5 ,a_6$
(表示 $1\mathrm{g}$ 砝码有 $a_1$ 个,$2\mathrm{g}$ 砝码有 $a_2$ 个,…,$20\mathrm{g}$ 砝码有 $a_6$ 个)
## 输出格式
输出方式:`Total=N`
($N$ 表示用这些砝码能称出的不同重量的个数,但不包括一个砝码也不用的情况)
## 样例 #1
### 样例输入 #1
```
1 1 0 0 0 0
```
### 样例输出 #1
```
Total=3
```
## 提示
**【题目来源】**
NOIP 1996 提高组第四题
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 int a[7] = {0,1,2,3,5,10,20} , num[10]; 5 ll dp[10010] , new_value[10010] , n , ans; 6 int main() 7 { 8 for(int i = 1; i <= 6; i++) 9 scanf("%d",&num[i]) , n += num[i]*a[i]; 10 dp[0] = 1; 11 int n_new = 0; 12 for(int i = 1; i <= 6; i++) 13 { 14 for(int j = 1; j <= num[i]; j <<= 1) 15 { 16 num[i] -= j; 17 new_value[++n_new] = j * a[i]; 18 } 19 if(num[i]) 20 { 21 new_value[++n_new] = num[i] * a[i]; 22 } 23 } 24 for(int i = 1; i <= n_new; i++) 25 for(int j = n; j >= 1; j--) 26 if(j >= new_value[i]) 27 dp[j] += dp[j - new_value[i]]; 28 for(int i = 1; i <= n; i++) 29 if(dp[i]) 30 ans++; 31 cout << "Total=" << ans << endl; 32 return 0; 33 }
其实我们可以想到,我们DP的自我滚动从n到1,是为了保证不会像dp[j+new_value[i]] += dp[j]的重复计算
我们从n到1会保证了每个只得到正确的计算次序!!!
加强理解
详见P2347 [NOIP1996 提高组] 砝码称重 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
标签:背包,二进制,value,##,砝码,new,优化,dp,mathrm From: https://www.cnblogs.com/smiling-weeping-zhr/p/17519830.html