codeforces

这题貌似写过= - =...
我们考虑取每个的价值,假设说我们取了第i个,其他个没有取.取第i个,其他不选,对于在取i的时间内是一种什么情况呢?
假设我们有两种选择,第一个时间是ti.另外一个时间是tj.第一个每分钟减少w[i],另外一个减少w[j].第一个完成的价值是val[i],另外一个完成的价值是val[j].考虑取这两个的先后顺序,似乎很简单分析,因为我们所用时间相同,那么其他产生的代价是一样的,我们可以不予考虑.假如说我先取i再取j,那么我获得的价值是val[i]+val[j]-(ti+tj)w[j]-tiw[i].
同理考虑先取j再取i就是val[j]+val[i]-(tj+ti)w[i]-tjw[j].
如此,我们就会发现其实就是和w[],t有关系,我们肯定会优先选取最优的然后再去填背包,如此我们就可以用01背包解决.上面式子把同类项消除得到就是相邻两项w[]和t[]的积,假如小就说明收益高.如此就可以很轻松的解决这题了.
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=55,M=100005;
struct vv{
    ll val,w,t;//分数 随时间减少的分数 时间
}a[N];
ll f[M];//背包.
bool cmp(vv x,vv y)
{
    return x.t*y.w<y.t*x.w;
}

int main()
{
    int n,T;
    //输入
    scanf("%d%d",&n,&T);
    for(int i=1;i<=n;i++)    scanf("%lld",&a[i].val);
    for(int i=1;i<=n;i++)    scanf("%lld",&a[i].w);
    for(int i=1;i<=n;i++)    scanf("%lld",&a[i].t);
    //排序
    sort(a+1,a+1+n,cmp);
    //背包容量是T,要求装的价值最高.
    for(int i=1;i<=n;i++)
    {
        for(int j=T;j>=a[i].t;j--)
        {
            f[j]=max(f[j],f[j-a[i].t]+a[i].val-j*a[i].w);
        }
    }
    ll ans=0;
    for(int i=T;i>=0;i--) ans=max(ans,f[i]);
    cout<<ans<<endl;
    return 0;
}