【Codeforces 730F】Ber Patio | Mrsrz's blog

贪心，动态规划。

题目大意：

你一开始有 $b$ 元的代金券。接下来有 $n$ 天，第 $i$ 天消费 $a_i$ 元。第 $i$ 天你可以使用至多 $\lfloor\frac {a_i}2\rfloor $ 元的代金券，剩下的部分需要支付现金。若你支付了 $x$ 元现金，则得到 $\lfloor\frac x {10}\rfloor$ 元代金券。

问你至少要付多少现金，并输出一种每天使用代金券数量的方案。

题解：

根据数据范围可知，总共得到的代金券的数量不超过 $10^4$。

令 $f_{i,j}$ 表示前 $i$ 天，总共得到 $j$ 元代金券，花费的最少现金。

那么状态 $i,j$ 剩下的代金券数量为 $j-\left(\sum_{k=1}^i a_k\right)+f_{i,j}$。

在不影响代金券总量的情况下，一张代金券早用和晚用是一样的，所以我们只需要记录最少现金即可。

然后枚举第 $i$ 天使用的现金个数进行转移即可。

直接做的复杂度是 $O(\left(\sum_{i=1}^n a_i\right)^2n)$。

这是个类似背包的转移，我们每次只转移 $\sum_{k=1}^i a_k$ 的状态，类似树上背包的，时间复杂度可优化至 $O(\left(\sum_{i=1}^n a_i\right)^2)$。常数大概 $\frac 1{20}$，可以通过。

记录状态的话，再开一个数组记录前驱状态即可。

开两个 $5000\times 10000$ 的 int 数组的空间可以接受。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
const int N=5050;
int n,b,a[N],dp[N][N*2],sum,ans[N];
short pre[N][N*2];
int main(){
    scanf("%d%d",&n,&b);
    for(int i=1;i<=n;++i)scanf("%d",a+i);
    memset(dp,-1,sizeof dp);
    **dp=0;
    int tot=0;
    for(int i=1;i<=n;++i){
        int*f=dp[i],*g=dp[i-1];
        tot+=a[i]/10;
        for(int j=0;j<=tot;++j)
            if(-1!=g[j])
                for(int k=a[i]+1>>1;k<=a[i]&&j+k/10<=tot;++k){
                    int ticket=b+j-(sum-g[j]);
                    if(a[i]-k>ticket)continue;
                    int nw=g[j]+k,&F=f[j+k/10];
                    if(!~F||F>nw)F=nw,pre[i][j+k/10]=j;
                }
        sum+=a[i];
    }
    int mx=1919810,p=0;
    for(int i=0;i<=10000;++i)if(mx>dp[n][i]&&~dp[n][i])
        mx=dp[n][i],p=i;
    for(int i=n;i;--i){
        int cost=dp[i][p]-dp[i-1][pre[i][p]];
        ans[i]=a[i]-cost;
        p=pre[i][p];
    }
    printf("%d\n",mx);
    for(int i=1;i<=n;++i)
        printf("%d ",ans[i]);
    return 0;
}