怪物猎人[贪心+dp]

$Solution$Solution

设当前砍到了第 $2$2 个怪物,
则 代价 为 $(a_i+d)(b_i+d)=a_i{b}_i+a_{i}d+d{b}_i+d^2=a_i{b}_i+d(a_i+b_i)+d^2$(ai​+d)(bi​+d)=ai​bi​+ai​d+dbi​+d2=ai​bi​+d(ai​+bi​)+d2
发现只有 $d(a_i+b_i)$d(ai​+bi​) 是会变的量, 基于 贪心 思路, 使 $(a_i+b_i)$(ai​+bi​) 在 $d$d 比较大时尽量小 .

于是按照 $a_i+b_i$ai​+bi​ 从大到小排序 $\left(第一步\right)$       (第一步)

光排序还不够, 还需要进行简单的 $dp$dp,
设 $dp[i,j]表示前i个砍j个所需要的最小代价$dp[i,j]表示前i个砍j个所需要的最小代价
$dp[i,j]=dp[i-1,j-1]+[a_i+(i-1\left)d\right]\ast [b_i+(i-1\left)d\right]$dp[i,j]=dp[i−1,j−1]+[ai​+(i−1)d]∗[bi​+(i−1)d]
得到 $dp[N,\mathrm{1...}N]$dp[N,1...N] 后 二分查找 即可

$Code$Code

#include<bits/stdc++.h>
#define reg register

typedef long long ll;

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

ll read_l(){
        char c;
        ll s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

const int maxn = 3005;

int N;
int M;
int D;

ll dp[maxn][maxn];

struct Node{ int a, b; } A[maxn];

bool cmp(Node x, Node y){ return x.a+x.b > y.a+y.b; }

int main(){
        freopen("hunter.in", "r", stdin);
        freopen("hunter.out", "w", stdout);
        N = read();
        M = read();
        D = read();
        for(reg int i = 1; i <= N; i ++) A[i].a = read();
        for(reg int i = 1; i <= N; i ++) A[i].b = read();
        std::sort(A+1, A+N+1, cmp);
        memset(dp, 0x3f, sizeof dp);
        for(reg int i = 0; i <= N; i ++) dp[i][0] = 0;
        for(reg int i = 1; i <= N; i ++)
                for(reg int j = 1; j <= i; j ++)
                        dp[i][j] = std::min(dp[i-1][j], dp[i-1][j-1] + 1ll*(A[i].a+1ll*D*(j-1))*(A[i].b+1ll*D*(j-1)));
        for(reg int i = 1; i <= M; i ++)
                printf("%d ", std::lower_bound(dp[N]+1, dp[N]+N+1, read_l())-dp[N]-1);
        return 0;
}