2015年1月1日 星期四

USACO 2014 March Contest, Silver Problem 3. Mooo Moo

// http://www.usaco.org/index.php?page=viewproblem2&cpid=417
#include <algorithm>
#include <iostream>
#include <cstdio>

using namespace std;

#define INF 2e9

int DP[200000];

int N, B;

int main()
{
    freopen("mooomoo.in", "r", stdin);
    freopen("mooomoo.out", "w", stdout);

    fill(DP, DP+200000, INF);
    DP[0] = 0;

    scanf("%d %d", &N, &B);

    for(int Bi = 0; Bi < B; Bi++)
    {
        int x;
        scanf("%d", &x);

        for(int i = x; i < 200000; i++)
            DP[i] = min(DP[i], DP[i-x]+1);
    }

    int now = 0, Ans = 0;

    for(int Ni = 0; Ni < N; Ni++)
    {
        int x;
        scanf("%d", &x);

        if( DP[x-now] == INF )
        {
            puts("-1");
            return 0;
        }

        Ans += DP[x-now];

        now = max(x-1, 0);
    }

    printf("%d\n", Ans);
}

沒有留言:

張貼留言