我没有想到怎么dp，怕是完了。。。（啊，只拿了5分。。。）
首先我们能发现
假设前面一个怪物为x1,y1后面一个怪物为x2,y2我们怎么确定如果两个怪物都要打先打前面那个？
列个式子如果前面一个先打前面一个耗费x1*y1+ad(x1+y1)+a^2*d^2后面一个则为x2*y2+bd(x2+y2)+b^2*d^2(a<b)因为最后所消耗的代价是它们的和所以可以发现区别就在x+y上，
我们只需要排个序将x+y从大到小排，然后用一个dp求出要在前j只怪物中选择i只怪物解决的时所需要的最小的生命值花费（这个就是背包吧。。。）
然后输进一个猎人的生命值再二分就可以了。
我很二地认为只要排过序后顺次取就可以了（然而并不能证明）
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<stack> #include<cstdlib> using namespace std; typedef long long ll; struct ding{ll a,b; }x[3009]; int n,m; ll d,dp[3009][3009],maxx; bool cmp(ding x,ding y) {return x.a+x.b>y.a+y.b; } inline int read() {char ch;ll ex=0;while ((ch<'0')||(ch>'9')) ch=getchar();while ((ch>='0')&&(ch<='9')) {ex=ex*10+ch-'0';ch=getchar();}return ex; } int check(ll p) {int l=1,r=n,tot=0;while (l<=r){int mid=(l+r)>>1;if (p<=dp[mid][n]) r=mid-1;else l=mid+1,tot=mid;}return tot; } int main() {scanf("%d%d",&n,&m);d=read();for (int i=1;i<=n;i++) x[i].a=read();for (int i=1;i<=n;i++) x[i].b=read();sort(x+1,x+1+n,cmp);for (int i=1;i<=n;i++)for (int j=i;j<=n;j++){ll pum=dp[i-1][j-1]+x[j].a*x[j].b+(i-1)*d*(x[j].a+x[j].b)+(i-1)*(i-1)*d*d;if (j!=i) dp[i][j]=min(pum,dp[i][j-1]);else dp[i][j]=pum;}for (int i=1;i<=m;i++) {ll h;scanf("%lld",&h);printf("%d ",check(h));}return 0; }