这其实是一道贪心题，而不是dp。
首先我们贪心的取有优惠券中价值最小的，并把这些东西都放在优先队列里，然后看[k + 1, n]中，有些东西使用了优惠券减的价钱是否比[1, k]中用了优惠券的物品更划算，是的话就更新。
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<vector> 9 #include<stack> 10 #include<queue> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a, x) memset(a, x, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const int INF = 0x3f3f3f3f; 19 const db eps = 1e-8; 20 const int maxn = 5e4 + 5; 21 inline ll read() 22 { 23 ll ans = 0; 24 char ch = getchar(), last = ' '; 25 while(!isdigit(ch)) {last = ch; ch = getchar();} 26 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();} 27 if(last == '-') ans = -ans; 28 return ans; 29 } 30 inline void write(ll x) 31 { 32 if(x < 0) x = -x, putchar('-'); 33 if(x >= 10) write(x / 10); 34 putchar(x % 10 + '0'); 35 } 36 37 int n, k; 38 ll m; 39 struct Node 40 { 41 ll c, p; 42 }t[maxn]; 43 44 bool cc(Node a, Node b) {return a.c < b.c;} 45 bool cp(Node a, Node b) {return a.p < b.p;} 46 47 priority_queue<ll, vector<ll>, greater<ll> > q; 48 49 int solve() 50 { 51 sort(t + 1, t + n + 1, cc); 52 ll sum = 0; 53 for(int i = 1; i <= k; ++i) 54 { 55 sum += t[i].c; 56 if(sum > m) return i - 1; 57 else if(i == n) return n; 58 q.push(t[i].p - t[i].c); 59 } 60 sort(t + k + 1, t + n + 1, cp); 61 int ans = k; 62 for(int i = k + 1; i <= n; ++i) 63 { 64 ll tp = q.empty() ? (ll)INF * (ll)INF : q.top(); 65 if(t[i].p - t[i].c > tp) 66 { 67 sum += tp + t[i].c; 68 q.pop(); q.push(t[i].p - t[i].c); 69 } 70 else sum += t[i].p; 71 if(sum > m) return ans; 72 ans++; 73 } 74 return ans; 75 } 76 77 int main() 78 { 79 n = read(); k = read(); m = read(); 80 for(int i = 1; i <= n; ++i) t[i].p = read(), t[i].c = read(); 81 write(solve()); 82 return 0; 83 }