//dp完全背包 //f[i] = max(f[i], f[i - value] + interest); //注意预处理每个value，由于他们都是1K的倍数，故都除以1K， //不处理会超时。 #include <iostream> #include <cmath> #include <cstring> using namespace std; struct node { int value; int interest; }data[10]; int f[50000]; int main() { //freopen("1.txt", "r", stdin); int t; cin >> t; while(t--) { int money, year; cin >> money >> year; int d; cin >> d; for(int i = 0; i < d; i++) { cin >> data[i].value >> data[i].interest; data[i].value /= 1000; } while(year--) { memset(f, 0, sizeof(f)); int t = money / 1000; for(int i = 0; i < d; i++) { for(int j = data[i].value; j <= t; j++) { f[j] = max(f[j], f[j - data[i].value] + data[i].interest); } } money += f[t]; } cout << money << endl; } return 0; }
