题目： https://ac.nowcoder.com/acm/problem/21314
牛牛正在打一场 C F CF CF比赛时间为 T T T分钟，有 N N N道题，可以在比赛时间内的任意时间提交代码。第 i i i道题的分数为 a [ i ] a[i] a[i]，题目的分数随着比赛的进行，每分钟减少 b [ i ] b[i] b[i]这是一场比较 d a r k dark dark的 C F CF CF，分数可能减成负数已知第 i i i道题需要花费 c [ i ] c[i] c[i]的时间解决请问最多可以得到多少分。
思路： 对于两道题 i , j i,j i,j来说，有两种先后顺序， x x x表示在 i , j i,j i,j之前的时间 t i m e 1 = a [ i ] + b [ j ] − ( x + c [ i ] ) b [ i ] − ( x + c [ i ] + c [ j ] ) b [ j ] i 在 j 前 t i m e 2 = a [ i ] + b [ j ] − ( x + c [ j ] ) b [ j ] − ( x + c [ i ] + c [ j ] ) b [ i ] j 在 i 前 time1=a[i]+b[j]-(x+c[i])b[i]-(x+c[i]+c[j])b[j]\quad i在j前\\ time2=a[i]+b[j]-(x+c[j])b[j]-(x+c[i]+c[j])b[i]\quad j在i前\\ time1=a[i]+b[j]−(x+c[i])b[i]−(x+c[i]+c[j])b[j]i在j前time2=a[i]+b[j]−(x+c[j])b[j]−(x+c[i]+c[j])b[i]j在i前 假设 i i i在 j j j前，则 t i m e 1 − t i m e 2 = c [ j ] b [ i ] − c [ i ] b [ j ] ≤ 0 ( 1 ) time1-time2=c[j]b[i]-c[i]b[j]\le 0\quad(1) time1−time2=c[j]b[i]−c[i]b[j]≤0(1) 所以只要按照式 ( 1 ) (1) (1)排序，然后判断每道题做不做，背包 d p dp dp即可。
#include<bits/stdc++.h> typedef long long ll; using namespace std; int N,T; const int maxn=55; const int maxt=1e5+5; ll dp[maxt]; struct node { int ma; int pm; int re; bool operator <(const node& rhs) const{ return pm*1.0/re > rhs.pm*1.0/rhs.re; } }nc[maxn]; int main() { cin>>N>>T; for(int i=0;i<N;i++) cin>>nc[i].ma; for(int i=0;i<N;i++) cin>>nc[i].pm; for(int i=0;i<N;i++) cin>>nc[i].re; sort(nc,nc+N); ll ans=0; for(int i=0;i<N;i++){ for(int j=T;j>=nc[i].re;j--){ dp[j]=max(dp[j],dp[j-nc[i].re]+nc[i].ma-nc[i].pm*j); ans=max(dp[j],ans); } } cout<<ans<<endl; }