首先，如果
n
n
n 个都要选，那么显然，应该先把
b
b
b 值大的先选掉，这样浪费最小。
基于这种想法之上，我们就可以先按 b 排个序，然后
d
p
dp
dp
用
f
i
,
j
f_{i,j}
fi,j 表示在前
i
i
i 个中选了
j
j
j 个的最大金币数
所以递推式就十分显然，
f
i
,
j
=
max
(
f
i
−
1
,
j
+
f
i
−
1
,
j
−
1
+
max
(
0
,
a
i
−
p
i
×
(
j
−
1
)
)
)
f_{i,j}=\max(f_{i-1,j}+f_{i-1,j-1}+\max(0,a_i-p_i\times (j-1)))
fi,j=max(fi−1,j+fi−1,j−1+max(0,ai−pi×(j−1)))
代码
#include<bits/stdc++.h>
using namespace std
;
int n
,k
,f
[1001][1001],ans
;
struct zj
{
int a
,p
;
}a
[1001];
bool cmp(zj a
,zj b
){return a
.p
>b
.p
;}
int get(){
memset(f
,0,sizeof(f
));
scanf("%d%d",&n
,&k
);
ans
=0;
if(!n
&&!k
)return 1;
for(int i
=1;i
<=n
;i
++)scanf("%d",&a
[i
].a
);
for(int i
=1;i
<=n
;i
++)scanf("%d",&a
[i
].p
);
sort(a
+1,a
+n
+1,cmp
);
for(int i
=1;i
<=k
;i
++)
for(int j
=1;j
<=n
;j
++)
f
[j
][i
]=max(f
[j
-1][i
],f
[j
-1][i
-1]+max(a
[j
].a
-a
[j
].p
*(i
-1),0));
for(int i
=1;i
<=k
;i
++)ans
=max(f
[n
][i
],ans
);
printf("%d\n",ans
);
return 0;
}
int main(){
while(!get());
}
