给出硬币面额及每种硬币的个数，求从1到m能凑出面额的个数。

多组数据，每组数据前两个数字为n，m。n表示硬币种类数，m为最大面额，之后前n个数为每种硬币的面额，后n个数为相应每种硬币的个数。
（n<=100,m<=100000，面额<=100000，每种个数<=1000）

RT

3 10

1 2 4 2 1 1

2 5

1 4 2 1

0 0

8

4


题解：
　　真是，先打了一个二进制分组t了，（本来可以过的吧！）。
　　正解是n×m的，首先，我们考虑设dp[i][j]表示凑出j这个数字最大还可以剩下几个i号硬币。这个可以省掉第一维.
　　dp[j]=-1表示不可以凑出来,转移就是if(dp[j]>=0) dp[j]=c[i];如果用前面的硬币就可以凑出来，那么i号硬币可以一个不用，if(dp[j]>0) dp[j+v[i]]=max(dp[j+v[i]],dp[j]-1);，然后就是很简单的用一个硬币。
　　初始化就是dp[0]=c[i]，表示凑出0还剩下c[i]个硬币。
代码：
二进制分组TLE

#include<iostream>

#include<algorithm>

#include<cstring>

#include<stdio.h>

#include<stdlib.h>

using namespace std;

int v[],num[],w[],dp[];

int n,m,cnt=;

int main(){

    while(){

        scanf("%d%d",&n,&m);

        if(!n&&!m) break;

        memset(dp,,sizeof(dp));

        dp[]=;cnt=;

        for(int i=;i<=n;i++) scanf("%d",&v[i]);

        for(int i=;i<=n;i++) scanf("%d",&num[i]);

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

            for(int j=;num[i]>;j*=){

                int x=min(num[i],j);

                num[i]-=x;

                w[++cnt]=x*v[i];

            }

        }

        for(int i=;i<=cnt;i++){

            for(int j=m;j>=w[i];j--){

                dp[j]|=dp[j-w[i]];

            }

        }

        int ans=;

        for(int i=;i<=m;i++) ans+=dp[i];

        printf("%d\n",ans);

    }

}

AC

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <iostream>

#define MAXN 100000+1

#define RG register

using namespace std;

int dp[MAXN],v[MAXN],c[MAXN];

int n,m;

int main()

{

    while(){

        scanf("%d%d",&n,&m);

        if(!n&&!m) break;

        for(int i=;i<=n;i++) scanf("%d",&v[i]);

        for(int i=;i<=n;i++) scanf("%d",&c[i]);

        memset(dp,-,sizeof(dp));

        dp[]=;

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

            for(RG int j=;j<=m;j++){

                if(dp[j]>=) dp[j]=c[i];

                else dp[j]=-;

            }

            for(RG int j=;j<=m-v[i];j++){

                if(dp[j]>) dp[j+v[i]]=max(dp[j+v[i]],dp[j]-);

            }

        }

        int ans=;

        for(int i=;i<=m;i++) if(dp[i]>=) ans++;

        printf("%d\n",ans);

    }

    return ;

}