题目描述

植物大战僵尸这款游戏中，还有一个特别的玩儿法：玩家操纵僵尸进攻植物。

首先，僵尸有m(m<=100)种（每种僵尸都是无限多的），玩家可以选择合适的僵尸来进攻。使用第i种僵尸需要花费Wi资源，可以得到Pi的攻击效果。在这里，我们认为多个僵尸总的攻击效果就是他们每个攻击效果的代数和。

地图共有n(n<=200000)行，对于第i行，最左端有若干植物，这些植物需要至少Qi的攻击才能被全部消灭。若一行上的植物全部被消灭，我们称这一行被攻破。

由于资源紧张，我们希望能够算出攻破所有行总共需要的最少的资源值K，你能算出K值来吗？

输入

第一行三个非负整数：m、n；

第二行m个正整数，第i个数表示Wi；

第三行m个正整数，第i个数表示Pi；

第四行n个非负整数，第i个数表示Qi。

输出

一个正整数K。

样例输入

3 4 5 2 11 3 1 7 10 3 2 4

样例输出

32 （样例说明：需要的最小代价是16+5+4+7=32。）

我的代码

#include<bits/stdc++.h>

using namespace std;

int m, n, w[109], p[109], q[200005], ans, f[200001];

int main()
{
	cin >> m >> n;
	for (int i = 1;i <= m;i ++)
	{
		cin >> w[i];
	}
	for (int i = 1;i <= m;i ++)
	{
		cin >> p[i];
	}
	for (int i = 1;i <= n;i ++)
	{
		cin >> q[i];
	}
	for (int i = 1;i <= n;i ++)
	{
		memset(f, 0, sizeof(f));
		for (int k = p[1];k <= q[i];k ++)
		{
			f[k] = max(f[k], f[k - p[1]] + w[1]);
		}
		for (int j = 1;j <= m;j ++)
		{
			for (int k = p[j];k <= q[i];k ++)
			{
				f[k] = min(f[k], f[k - p[j]] + w[j]);
			}
		}
		ans += f[q[i]];
	}
	cout << ans;
	return 0;
}