Category Archives: Dynamic Programming

USACO 3.3.2 – Special Offers

#include <iostream>
#include <cstdio>
#include <algorithm>
struct offer {
	int N, c, p[5], a[5];
} offers[100];
int id[5], c[5] = { 0 }, num[5], map[1001];
int dp[6][6][6][6][6]={{{{{0}}}}}, O,N,i,j,valid=1,T=0,best=0;
using namespace std;

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

	for (scanf("%d", &O), i = 0; i < O; scanf("%d", &offers[i].c), i++)
		for (j = 0, scanf("%d", &offers[i].N); j < offers[i].N; j++)
			scanf("%d %d", offers[i].p + j, offers[i].a + j);
	for (scanf("%d", &N), i = 0; i < N; map[id[i]] = i, i++)
		scanf("%d %d %d", id + i, num + i, c + i);

	for (int m = 100001, t[5] = { 0 }; m <= 155555; m++, valid =(T = best = 0)+1) {
		for (int n = m; (n / 10) && valid; n /= 10, T++)
			t[T]= n%10, best +=(t[T] * c[T]), valid &= t[T] <= 5;

		if (!valid) continue;

		for (int o = 0; o < O; o++)
			for (int n=0,a[5]={0}, s[5], good = 1; n < offers[o].N; n++) {
				if (map[offers[o].p[n]] != -1)
					a[map[offers[o].p[n]]] = offers[o].a[n];
				for (int q = 0; q < 5; q++)
					good &= t[q] >= a[q], s[q]=t[q]-a[q];
				if (good)
					best = min(best,offers[o].c+dp[s[0]][s[1]][s[2]][s[3]][s[4]]);
			}
		dp[t[0]][t[1]][t[2]][t[3]][t[4]] = best;
	}
	printf("%d\n", dp[num[0]][num[1]][num[2]][num[3]][num[4]]);
}
Advertisements

USACO 3.2.2 – Stringsobits

#include <cstdio>
#include <algorithm>

int main() {
	freopen("kimbits.in", "r", stdin), freopen("kimbits.out", "w", stdout);
	unsigned N, L, I, sum[33][33];
	scanf("%u %u %u", &N, &L, &I);

	for (int i = 0; i < 33; i++)
		for (int j = 0; j < 33; j++)
			sum[i][j] = j && i ? sum[i - 1][j] + sum[i - 1][j - 1] : 1;

	for (int i = N, b = I > sum[i - 1][L]; i >= 1; i--, b = I > sum[i - 1][L])
		putchar('0' + b), I -= b ? sum[i - 1][L] : 0, L -= b;

	putchar('\n');
}

USACO 3.1.6 – Stamps

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
	freopen("stamps.in", "r", stdin), freopen("stamps.out", "w", stdout);
	int MAX= 2000001, j, K, N, i , coins[51];
	unsigned char count[2000001] = {0};
	scanf("%d %d", &K, &N);
	for (i = 0; i < N; i++) scanf("%d", coins+i);
	
	for(i=1, count[1]=201; i<MAX; i++, count[i]=201)
		for(j=0; j<N ; j++)
			if(i>=coins[j])
				count[i] = min(int(count[i]), int(count[i-coins[j]])+1);
	
	for(i=1; count[i]<=K; i++)
		;

	printf("%d\n", i-1);
}

USACO 3.1.3 – Humble Numbers


#include <cstdio>
using namespace std;

int main() {
	freopen("humble.in", "r", stdin), freopen("humble.out", "w", stdout);
	int INF =(1 << 31) -1, K, N, h, p, humble[100001], pos[101] = {0}, prime[101];
	scanf("%d %d", &K, &N);
	for (h = 1; h <= K; h++)
		scanf("%d", prime+h);

	for (humble[0] = 1, h = 1; h <= N; h++) {

		for (humble[h] = INF, p = 1; p <= K; p++)
			humble[h] = min(humble[h], prime[p] * humble[pos[p]]);

		for (p = 1; p <= K; p++)
			pos[p] += humble[h] >= prime[p] * humble[pos[p]];
	}
	printf("%d\n", humble[N]);
}

USACO 3.1.2 – Score Inflation

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
	freopen("inflate.in", "r", stdin), freopen("inflate.out", "w", stdout);
	int M, N, w[10001], c[10001], best[10001];
	scanf("%d %d\n%d %d\n", &M, &N, w, c);

	for (int i = 0; i < N; i++, scanf("%d %d\n", w+i, c+i))
		for (int j = c[i]; j <= M; j++)
			best[j] = max(best[j], best[j - c[i]] + w[i]);

	printf("%d\n", best[M]);
	return 0;
}

USACO 2.3.4 – Money System


#include <cstdio>
using namespace std;

int main() {
	long long int N, V, v[26] = { 0 }, dp[10001] = { 0 }, i;
	freopen("money.in", "r", stdin), freopen("money.out", "w", stdout);
	scanf("%lld %lld", &V, &N);
	for (i = 0, dp[0] = 1; i < V; i++)
		scanf("%lld", v + i);

	for (int m = 0; m < V; m++)
		for (int n = 0; n <= N; n++)
			dp[n] += (n - v[m] >= 0 ? dp[n - v[m]] : 0);

	printf("%lld\n", dp[N]);
	return 0;
}

USACO 2.3.2 – Cow Pedigrees

#include <cstdio>
#include <iostream>

using namespace std;

int main() {
	int dp[101][202]={{0}}, N, K;
	freopen("nocows.in", "r", stdin), freopen("nocows.out", "w", stdout);
	scanf("%d %d", &N, &K);

	for(int i=1; i<=K; i++)
		dp[i][0] = dp[i][1] = 1;

	for(int h=1; h<=K; h++)
		for(int n=1; n<=N; n+=2)
			for(int c=1; c<n; c+=2)
				dp[h][n] = (dp[h][n] + dp[h-1][c]*dp[h-1][n-c-1])%9901;

	cout << (dp[K][N] - dp[K-1][N] + 9901)%9901 << endl;
	return 0;
}

USACO 2.2.2 – Subset Sums

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;

int main() {
	int n;
	freopen("subset.in", "r", stdin), freopen("subset.out", "w", stdout);
	scanf("%d", &n);
	long long int dp[400] = { 0 }, sum = (n * (n + 1))/2;
	dp[0] = 1;
	for (int i = 1; i <= n; i++)
		for (int s = sum/2; s >= i; s--)
			dp[s] += dp[s - i];

	printf("%lld\n", (sum%2? 0 : dp[sum/2] / 2));
	return 0;
}

UVa – 10926 – How Many Dependencies?


#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

int dist[101][101];

int main() {

	for (int N, max_deps = 0, max_i = 0; scanf("%d", &N) && N; max_deps = 0, max_i = 0) {
		memset(dist, 0, sizeof dist);
		
		for (int T, n = 1; n <= N && scanf("%d", &T); n++)
			for (int t = 1, o; t <= T && scanf("%d", &o); t++)
				dist[n][o] = 1;

		for (int k = 1; k <= N; k++)
			for (int i = 1; i <= N; i++)
				for (int j = 1; j <= N; j++)
					if ((dist[i][k] * dist[k][j] != 0) && (i != j) && dist[i][k] + dist[k][j] >= dist[i][j]) {
						dist[i][j] = dist[i][k] + dist[k][j];
						if (dist[i][j] > max_deps || (dist[i][j] == max_deps && i < max_i))
							max_i = i, max_deps = dist[i][j];
					}

		printf("%d\n", max_i);
	}
	return 0;
}

UVA – 435 – Dividing Coins

 #include &lt;stdio.h&gt;<br /><br />#include &lt;iostream&gt;<br /><br />#include &lt;algorithm&gt;<br /><br />#include &lt;math.h&gt;<br /><br />#include &lt;string.h&gt;<br /><br />#include &lt;string&gt;<br /><br />#include &lt;set&gt;<br /><br />#include &lt;map&gt;<br /><br />using namespace std;<br /><br />#define lop(ii, ii0, iin) for(ii=ii0; ii&lt;iin; ++ii)<br /><br />#define rep(ii, NN) lop(ii, 0, NN)<br /><br />int a[105], v[25005], i, j, half;<br /><br />int main() {<br /><br />int T, N, sum,t;<br /><br />scanf("%d", &amp;T);<br /><br />while (T-- &amp;&amp; scanf("%d", &amp;N) &amp;&amp; !(sum = 0)) {<br /><br />memset(v, 0, sizeof v);<br /><br />rep(i, N)<br /><br />t = scanf("%d", a + i), sum += a[i];<br /><br />half = sum / 2, v[0] = 1;<br /><br />rep(i, N)<br /><br />for (j = half; j &gt;= 1; j--)<br /><br />v[j] |= (a[i] &lt;= j ? v[j - a[i]] : false);<br /><br />for (j = half; j &gt;= 1; j--)<br /><br />if (v[j]) break;<br /><br />printf("%d\n", sum - 2 * j);<br /><br />}<br /><br />return 0;<br /><br />}<br /><br />