POJ 1742 Coins 【DP】

tonyfang posted @ 2016年4月03日 15:27 in poj with tags C++ OI , 494 阅读

很容易想到dp。然后方程随便列啦

# include <stdio.h>
# include <string.h>
using namespace std;
int n, m, v[105], c[105], f[100005], times[100005];
int main() {
	while(1) {
		scanf("%d%d", &n, &m);
		if(n+m == 0) break;
		for (int i=1; i<=n; ++i) scanf("%d", &v[i]);
		for (int i=1; i<=n; ++i) scanf("%d", &c[i]);
		memset(f, 0, sizeof(f));
		f[0]=1;
		int ans=0;
		for (int i=1; i<=n; ++i) {
			memset(times, 0, sizeof(times));
			for (int j=v[i]; j<=m; ++j)
				if(!f[j] && f[j-v[i]] && times[j-v[i]] < c[i]) f[j] = 1, times[j] = times[j-v[i]] + 1, ans++;
		}
		printf("%d\n", ans);
	}
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter