dp题集

acm 题集 dp

HDU 2844 Coins

#include<iostream>  
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<bitset>
#include<numeric>
#include<vector>
#include<string>
#include<iterator>
#include<cstring>
#include<functional>
#define INF 0x3f3f3f3f
#define ms(a,b) memset(a,b,sizeof(a))
#define pi 3.14159265358979
#define mod 1000000007
#define maxn 100010
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
typedef unsigned long long ull;
int n, m, c[maxn], v[maxn], d[maxn];
void zeroonepack(int cost, int weight)
{
    for (int i = m; i >= cost; i--)
    {
        d[i] = max(d[i], d[i - cost] + weight);
    }
}
void completepack(int cost, int weight)
{
    for (int i = cost; i <= m; i++)
    {
        d[i] = max(d[i], d[i - cost] + weight);
    }
}
void multipack(int cost, int weight, int amount)
{
    if (cost*amount >= m)
        completepack(cost, weight);
    else
    {
        int k = 1;
        while (k <= amount)
        {
            zeroonepack(k*cost, k*weight);
            amount -= k;
            k *= 2;
        }
        zeroonepack(amount*cost, amount*weight);
    }
}
int main()
{
    while (cin >> n >> m)
    {
        if (!n && !m) break;
        ms(d, 0);
        for (int i = 0; i < n; i++)
        {
            cin >> v[i];
        }
        for (int i = 0; i < n; i++)
        {
            cin >> c[i];
        }
        for (int i = 0; i < n; i++)
        {
            multipack(v[i], v[i], c[i]);
        }
        int sum = 0;
        for (int i = 1; i <= m; i++)
        {
            if (d[i] == i)
                sum++;
        }
        cout << sum << endl;
    }
}

#