USACO BRHS10A Problem 'potatoes' Analysis

by Damon Doucet

If you wanted to solve only the first 80% of the test cases, then you could use recursion. A sample recursive function to accomplish this might be the following:

int P, R, D, N[105], C[105];

int M(int i) {
    if (i == 0) return 0; //it costs 0 to buy 0 potatoes
    int ret = R + M(i - 1);

    for (int j = 0; j < D; j++) {
        if (N[j] > i) continue;
        ret = min(ret, M(i - N[j]) + C[j]);
    }

    return ret;
}

However, this is too slow for the last few cases. In order to solve those, you must use dynamic programming.

Dynamic programming is a way to turn the exponential times of recursion into polynomial times (like linear or quadratic, for example). You can see in my solution below how this particular problem would be converted from recursion to dynamic programming.

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

int P, R, D, N[105], C[105], M[10005];
ifstream fin("potatoes.in");
ofstream fout("potatoes.out");

int main() {
	int i, j;

	fin >> P >> R >> D;
	for (i = 0; i < D; i++)
		fin >> N[i] >> C[i];

	M[0] = 0; //It costs 0 moneys to buy 0 potatoes
	for (i = 1; i <= P; i++) {
		M[i] = M[i-1] + R;
		for (j = 0; j < D; j++) {
			if (N[j] > i) continue;
			M[i] = min(M[i], M[i - N[j]] + C[j]);
		}
	}

	fout << M[P] << "\n";
}