POJ 1742 Coins DP 01背包

dp[i][j]表示前i种硬币中取总价值为j时第i种硬币最多剩下多少个，-1表示无法到达该状态。

a.当dp[i-1][j]>=0时，dp[i][j]=ci;

b.当j-ai>=0&&dp[i-1][j-ai]>0时，dp[i][j]=dp[i-1][j-ai]-1;

c.其他，dp[i][j]=-1

Source Code

Problem:         User: BMan

Memory: 1112K        Time: 1547MS

Language: G++        Result: Accepted

Source Code

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<iostream>

#include<sstream>

#include<cmath>

#include<climits>

#include<string>

#include<map>

#include<queue>

#include<vector>

#include<stack>

#include<set>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

#define pb(a) push(a)

#define INF 0x1f1f1f1f

#define lson idx<<1,l,mid

#define rson idx<<1|1,mid+1,r

#define PI  3.1415926535898

template<class T> T min(const T& a,const T& b,const T& c) {

    return min(min(a,b),min(a,c));

}

template<class T> T max(const T& a,const T& b,const T& c) {

    return max(max(a,b),max(a,c));

}

void debug() {

#ifdef ONLINE_JUDGE

#else

    freopen("d:\\in1.txt","r",stdin);

    freopen("d:\\out1.txt","w",stdout);

#endif

}

int getch() {

    int ch;

    while((ch=getchar())!=EOF) {

        if(ch!=' '&&ch!='\n')return ch;

    }

    return EOF;

}

const int maxn=;

const int maxm=;

int c[maxn],a[maxn];

int dp[maxm];

int main()

{

    //freopen("data.in","r",stdin);

    int n,m;

    while(cin>>n>>m)

    {

        if(n&&m);else break;

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

            cin>>a[i];

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

            cin>>c[i];

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

        dp[]=;

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

        {

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

            {

                if(dp[j]>=)

                    dp[j]=c[i];

                else if(j>=a[i]&&dp[j-a[i]]>)

                    dp[j]=dp[j-a[i]]-;

            }

        }

        int cnt=;

        for(int i=;i<=m;i++)

            if(dp[i]>=)

                cnt++;

        cout<<cnt<<endl;

    }

    return ;

}