微扰贪心 and DP

前置知识 微扰贪心

例题 国王游戏 耍杂技的牛

耍杂技的牛 证明

DP

codeforces

分析

对于两道题t1,t2来说，有两种做题顺序，如下图的C12,C21,我们定义P1为t1的每分钟减小的分数，T1为做题需要的时间

两道题的初始总分数为sum(最大分数之和）
则
得分C12=sum-T1P1-(T1+T2)P2;
得分C21=sum-T2P2-(T1+T2)P1;
则 C12-C21=T2P1-T1P2
要判断两道题的大小，这上式同时除T1*T2的P1/T1-P2/T2 这样我们就发现了优先级函数为P/T即每分钟减小分数除需要的做题时间

代码

/*made in mrd*/
#include
using namespace std;
const int N=2e5+10;
#define int long long
#define mem(a,b) memset(a,b,sizeof a)
#define fi first
#define se second
#define pii pair
#define pb push_back
int dp[N];
struct node{
    int x,y,z;
    bool operator <(const node &p) const{
       return y*1.0/z>p.y*1.0/p.z;
    }
}a[N];
signed main() {
int n,T;
cin>>n>>T;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x;
    }
    for(int i=1;i<=n;i++)
        cin>>a[i].y;
    for(int i=1;i<=n;i++)
    cin>>a[i].z;
    sort(a+1,a+n+1);
    
    mem(dp,-0x3f);
    dp[0]=0;   
    for(int i=1;i<=n;i++)
    {

        for(int j=T;j>=a[i].z;j--)
        {
           
            dp[j]=max(dp[j],dp[j-a[i].z]+a[i].x-a[i].y*j);
        }
    }
    int res=0;
    for(int i=1;i<=T;i++)
    res=max(dp[i],res);
    cout<