(UVA) 11517 - Exact Change

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=2512&mosmsg=Submission+received+with+ID+17707369

dp一番即可

O(n * 10000)

#include <iostream>
#include <stdio.h>
#include <utility>
using namespace std;

typedef pair<int,int> pii;
const int MAX_N = 103;
const int MAX_V = 10003;

pii dp[MAX_N][2*MAX_V];
int w[MAX_N],v[MAX_N];

pii operator+(const pii &p1,const pii &p2) {
 return make_pair(p1.first+p2.first,p1.second+p2.second);
}

int main () {
 int T;
 scanf("%d",&T);
 while (T--) {
  int p;
  scanf("%d",&p);
  int n;
  scanf("%d",&n);
  for (int x=1;n>=x;x++) {
   scanf("%d",&w[x]);
   v[x]=w[x];
  }
  for (int x=1;n>=x;x++) {
   for (int y=1;2*MAX_V>y;y++) {
    dp[x][y]=make_pair(0,0);
   }
  }
  for (int i=1;n>=i;i++) {
   for (int j=1;2*MAX_V>j;j++) {
    if (j-w[i] < 0) dp[i][j]=dp[i-1][j];
    else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+make_pair(v[i],-1));
   }
  }
  pii ans=dp[n][p];
  if (ans.first==p) {
   printf("%d %d\n",ans.first,-ans.second);
  }
  else {
   int id=p+1;
   while (1) {
    if (dp[n][id].first>=p) {
     ans=dp[n][id];
     printf("%d %d\n",ans.first,-ans.second);
     break;
    }
    id++;
   }
  }
 }
}