Little Sub and Piggybank （杭师大第十二届校赛G题） DP

题意：每天能往存钱罐加任意实数的钱，每天不能多于起那一天放的钱数。如果某一天的钱数恰好等于那天的特价商品，则可以买，求最后的最大快乐值。

思路：先来一段来自出题人的题解：

　　显然的贪心：如果第$i$天买完，准备在第$j$天买，那么显然最优是在$i+1$到j天放$wi/(j-i)$的钱。于是假定选择的物品是$k1,k2,k3… $那么必须满足：

　　$a[k_i]/(k_i-k_i-1)<=a[k_i-1]/(k_i-1-k_i-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<bits/stdc++.h>
#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<i;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
",ans);
    }
    return 0;
}

View Code