3544. 小迷妹在哪儿 DP 01背包变体 贪心

3544. 小迷妹在哪儿 DP 01背包变体 贪心

小迷妹在哪儿
选择相同迷妹的情况下，交换任意两个小迷妹的顺序可以列不等式证明性价比高的先找更优

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct fan{int score;int time;
};
bool cmp(fan a,fan b){              //按性价比排序return a.score*b.time>b.score*a.time;
}
int main(){int n,T;cin>>n>>T;vector<fan> fans(n+1);for(int i=1;i<=n;++i){scanf("%d%d",&fans[i].score,&fans[i].time);}sort(fans.begin()+d() ,cmp);     //先考虑性价比高的，保证前面的dp结果是最优子结构vector<int>dp(T+1);int maxl=0;;for(int i=1;i<=n;++i){for(int j=T;j>=fans[i].time;--j){dp[j]=max(dp[j],dp[j-fans[i].time]+fans[i ].score*(T-j));//考虑第抓不抓i号迷妹情况下，dp[j]表示T的时限下，j的时间抓完迷妹的得到的最高分，如果抓考虑性价比也是i号迷妹最后抓完，前面抓的都是性价比比他高的maxl=max(maxl,dp[j]);}}cout<<maxl<<endl;return 0;
}