题目传送门
题意：每天能往存钱罐加任意实数的钱，每天不能多于起那一天放的钱数。如果某一天的钱数恰好等于那天的特价商品，则可以买，求最后的最大快乐值。
思路：先来一段来自出题人的题解：
显然的贪心：如果第$i$天买完，准备在第$j$天买，那么显然最优是在$i+1$到j天放$wi/(j-i)$的钱。 于是假定选择的物品是$k1,k2,k3… $那么必须满足：
$a[ki]/(ki-ki-1)<=a[ki-1]/(ki-1-ki-2)$
令$f[i][j]$表示最后购买的两个物品为i和j，则$f[i][j]=max(f[j][k]+v[i])$ (j->k->i合法) 观察到上述条件可以把k分离，即$k>=j-(i-j)*a[j]/a[i]$，因此可以维护前缀和来使得时间复杂度变为$O(n2)$。
这是来自zju的cjb学长的题解，接下来是我对这道题的一些理解。
$f[i][j]$最后一次买的是第i个物品，前一次是第j个物品的最大收益，那么我们就有$f[i][j]=max(f[j][k]+v[i])$并且i，j，k要合法，合法的条件就是$a[i]/(i-j)<=a[j]/(j-k)$，那么我们把这个式子移一下项，就得到了合法条件是$k>=j-(i-j)*a[j]/a[i]$，然后我们用$g[j][k]$表示，以k为起点，所有买了j物品的最大的f[j][k]，即$g[j][k]=max(f[j][k])$,然后同时维护$f$和$g$两个结构就可以了。
#include
#define clr(a,b) memset(a,b,sizeof(a))
typedef
long
long
ll;
using
namespace
std;
const
int maxn=
2010
;
int
n,f[maxn][maxn],g[maxn][maxn],ans,a[maxn],v[maxn],k;
int
main(){
while(cin>>
n) {
for(
int i=
1;i<=n;i++
) { cin>>
a[i]; }
for(
int i=
1;i<=n;i++
) { cin>>
v[i]; } clr(f,
0),clr(g,
0
);
for(
int i=
1;i<=n;i++
) { f[i][
0]=
v[i];
for(
int j=
1;j
) {
if(!a[i])k=
0
;
else k=max(ceil(j-
1.0*a[j]/a[i]*(i-j)),
0.0
);
if(j>=k&&
g[j][k]) f[i][j]=max(f[i][j],g[j][k]+
v[i]); }
for(
int j=i-
1;j>=
0;j--
) { g[i][j]=max(g[i][j+
1
],f[i][j]); } } ans=
0
; rep(i,
1,n)ans=max(ans,g[i][
0
]); printf(
"
%d\n
"
,ans); }
return
0
; }
View Code
转载于:https://www.cnblogs.com/mountaink/p/10561532.html
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/211478.html原文链接：https://javaforall.net
