传送门：题目详情 - 存钱罐 - JMYSOJ (jmfes.com)

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

const int N = 1e4 + 5; const int inf = 0x3f3f3f3f;

int dp[N];

int main() { memset(dp, inf, sizeof(dp)); dp[0] = 0; int a, b; cin >> a >> b; int v = b - a; int n; cin >> n; for (int i = 0; i < n; ++i) { cin >> a >> b; for (int j = b; j <= v; j ++) { if(dp[j - b] != inf){ dp[j] = min(dp[j - b] + a , dp[j]); } } } if (dp[v] == inf) { cout << "impossible." << endl; } else { cout << dp[v] << endl; } return 0; }

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

const int N = 1e4 + 5; const int inf = 0x3f3f3f3f;

int f[N];

int main() { memset(f, inf, sizeof(f)); f[0] = 0; int a, b; cin >> a >> b; int v = b - a; int n; cin >> n; for (int i = 0; i < n; ++i) { cin >> a >> b; for(int j = b; j <= v; j ++){ if(f[j - b] != inf){ f[j] = min(f[j], f[j - b] + a); } } } if (f[v] == inf) { cout << "impossible." << endl; } else { cout << f[v] << endl; } return 0; }