原文链接https://www.cnblogs.com/zhouzhendong/p/SRM502-500.html

SRM502 Div1 500

好题。

首先，如果已经确定了解决所有问题的优先级，只需要对于每一个问题是否被解决做出决策，那么显然直接 01 背包就好了。

事实上，我们是可以贪心地确定两个问题的优先程度的。

对于两个问题，假设分别为 a 和 b，则先做 a 再紧接着做 b 和先做 b 再紧接着做 a 的收益之差为

设 先做 a 再紧接着做 b 优于 先做 b 再紧接着做 a ，那么

如果我们称在一种方案中，a 先于 b 做，但不满足上式时，ab 为一对逆序对，那么：

不失一般性，对于某一种方案的任何相邻的逆序对都执行交换操作后，这种方案中依次进行的决策的相邻元素都满足上式，等价于按照上式所述的特殊值排序。

于是我们就确定了所有问题的优先级，再套个 01 背包即可解决这个问题。

static const int N=55,TT=100005*2;

static const LL INF=1LL<<56;

int n;

LL dp[TT];

int find(int T, vector <int> a, vector <int> d, vector <int> r){

    n=a.size();

    for (int i=0;i<n;i++)

        for (int j=i+1;j<n;j++)

            if (1LL*r[j]*d[i]<1LL*r[i]*d[j]){

                swap(a[i],a[j]);

                swap(d[i],d[j]);

                swap(r[i],r[j]);

            }

    for (int i=0;i<TT;i++)

        dp[i]=-INF;

    dp[0]=0;

    for (int i=0;i<n;i++)

        for (int j=T-1;j>=0;j--)

            dp[j+r[i]]=max(dp[j+r[i]],dp[j]+a[i]-1LL*d[i]*(j+r[i]));

    LL ans=-INF;

    for (int i=0;i<=T;i++)

        ans=max(ans,dp[i]);

    return ans;

}