洛谷P2214 [USACO14MAR]哞哞哞Mooo Moo（完全背包）

設a[i]為第i個農場的總音量，如果我們将a[i]減去a[i-1]-1（前提是a[i-1]不為0），設最終為b[i]，就不難發現，其實就相當于完全背包問題，要我們用B種物品去，以最少的數量去填滿容量為b[i]的背包。是以，我們隻需對逐個弄場求完全背包，把最終結果相加即可。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=1e5+5;
int dp[maxn],a[105],b[105],w[25];

int main()
{
	int n,B;
	cin>>n>>B;
	for(int i=1;i<=B;++i)	cin>>w[i];
	a[0]=0;
	for(int i=1;i<=n;++i)
	{
		cin>>a[i];
		b[i]=a[i];
		if(a[i-1])	b[i]-=(a[i-1]-1);
	}
	int ans=0;
	for(int i=1;i<=n;++i)
	{
		for(int j=0;j<=b[i];++j)	dp[j]=inf;	//初始化為inf
		dp[0]=0;	//dp[0]一定要為0
		for(int j=1;j<=B;++j)
			for(int k=w[j];k<=b[i];++k)
				dp[k]=min(dp[k],dp[k-w[j]]+1);
		if(dp[b[i]]==inf)	
		{
			ans=-1;
			break;
		}
		ans+=dp[b[i]];
	}
	cout<<ans<<endl;
	return 0;
}