USACO 3.1 Stamps

Dynamic programming problem. Let dp[i] denotes the minimum number of stamps required to construct a value of i. Then the state transfer function is dp[i] = min(dp[i - val[j]) + 1 for all j between 1 and N, where i >= val[j].

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>
#include <cmath>
#include <string>
#include <map>
#include <unordered_map>
#include <climits>
#include <sstream>

using namespace std;

int K, N;
int main() {
  ifstream fin("stamps.in");
  ofstream fout("stamps.out");
  fin >> K >> N;
  vector<int> val(N, 0);
  for (int i = 0; i < N; ++i) {
    fin >> val[i];
  }
  vector<int> dp(2000001, INT_MAX);
  dp[0] = 0;
  int i = 0;
  while (dp[i] <= K) {
    ++i;
    int cur = INT_MAX;
    for (int j = 0; j < N; ++j) {
      if (val[j] > i) continue;
      cur = std::min(cur, dp[i - val[j]]);
    }
    dp[i] = cur + 1;
  }
  
  fout << i - 1 << endl;
  cout << i - 1 << endl;
}