題意：給你一定數量和面值的紙幣，在不超過總錢數m的情況下，用所給的紙幣共能形成多少種錢數
思路：本來想到多重背包上面了，用多重背包寫了一下，tle，後來用二進制優化，還是tle，後來看dis，說用優先隊列，網上搜資料，沒看懂，，後來看acmj1991的博客，說是用數組標記法，然後不懂神馬是數組標記法。後來才知道，其實就是個常規的方法，不過很強大。具體來說，對於每件物品，循環錢數從自身價值一直到總價值，每次循環時判斷，若該值沒出現過，則ans加1.用flag[i]標記i這個值是否出現過，num[i]表示當前物品的價值，sum表示當前物品的數量，則if(flag[i - num[i]] && cnt[i - num[i]] < sum && !flag[i])成立時，ans加1。其中cnt[i]表示當前物品所形成的價值為i時所用的當前物品的數量。
代碼：
[cpp]
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
const int N = 100010;
int num[110];
bool flag[N];
int cnt[N];
int main(){
//freopen("1.txt","r",stdin);
int n,totalvalue;
while(scanf("%d%d",&n,&totalvalue)&&n&&totalvalue){
for(int i = 0;i < n;++i)
scanf("%d",&num[i]);
CLR(flag,false);
flag[0] = true;
int sum = 0,ans = 0;
for(int i = 0;i < n;++i){
scanf("%d",&sum);
CLR(cnt,0);
for(int j = num[i];j <= totalvalue;++j){
if(flag[j-num[i]] && cnt[j-num[i]] < sum && !flag[j]){
flag[j] = true;
ans++;
cnt[j] = cnt[j-num[i]] + 1;
}
}
}
printf("%d\n",ans);
}
return 0;
}
作者：wmn_wmn
