By tinylic

如果没有b[i]这个属性的话就是明显的01背包问题。

现在考虑相邻的两个物品x,y。假设现在已经耗费p的时间，那么分别列出先做x,y的代价：

a[x]-(p+c[x])*b[x]+a[y]-(p+c[x]+c[y])*b

a[y]-(p+c[y])*b[y]+a[x]-(p+c[y]+c[x])*b

对这两个式子化简，得到①＞②的条件是c[x]*b[y]<c[y]*b[x].

发现只要满足这个条件的物品对(x,y)，x在y前的代价永远更优。

因此可以根据这个条件进行排序，之后就是简单的01背包了。

 

然而我看这个DP方程还不是完全的01背包，应该是 f[i] 表示到时刻 i 的最优解，且时刻 i 必须得用

代码

#include 
     
      #include 
      
       #include 
       
        #define N 100001#define LL long long#define max(x, y) ((x) > (y) ? (x) : (y))int T, n;LL ans, f[N];struct node{    LL a, b, c;}p[51];inline int read(){    int x = 0, f = 1;    char ch = getchar();    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;    for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';    return x * f;}inline bool cmp(node x, node y){    return x.c * y.b < y.c * x.b;}int main(){    int i, j;    T = read();    n = read();    for(i = 1; i <= n; i++) p[i].a = read();    for(i = 1; i <= n; i++) p[i].b = read();    for(i = 1; i <= n; i++) p[i].c = read();    std::sort(p + 1, p + n + 1, cmp);    for(i = 1; i <= n; i++)        for(j = T; j >= p[i].c; j--)        {            f[j] = max(f[j], f[j - p[i].c] + p[i].a - j * p[i].b);            ans = max(ans, f[j]);        }    printf("%lld\n", ans);    return 0;}