题解 P7129 【「RdOI R1」冰淇淋游戏(play)】

dead_X · 2020-12-20 10:35:55 · 题解

前言

我是屑我是屑我是屑

我连多重背包01拆分都能写错

啊啊啊啊啊啊啊啊啊啊啊啊啊

思路

二合一题。

任务 1：计算一关的最大分数

一个很显然的 dp，我用了记忆化搜索实现。显然对于一个区间 [l,r]，最后选的数只能是 a_l 或者 a_r，而最后选的数会创造 r-l+1 的贡献。因此得到一个很显然的柿子：

dp_{i,j}=\max\{dp_{i+1,j}+a_i\times(j-i+1),dp_{i,j-1}+a_j\times (j-i+1)\}

任务 2：计算总分最大值

显然直接二进制分组多重背包即可。

一个小坑：这里的多重背包需要将前面所有的都选至少一次，所以 dp 的时候要先强制选一次，再自由选。

来讲一下我犯的 nt 错误：
大家都知道完全背包应该是

for(int i=1; i<=mx; mx-=i,i<<=1) 做一次i个物品的完全背包;
做一次mx个物品的完全背包;

然后我写了个

for(int i=1; i<=mx; i<<=1) if(i&mx) 做一次i个物品的完全背包;

一定要记住二进制拆分的原理啊/kel

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int c,mx,m,sdt,a[503];
long long dp[503][503];
long long ans[100003][2],Ans=0;
long long dfs(int l,int r)
{
if(l==sdt&&r==sdt) return a[sdt];
if(dp[l][r]) return dp[l][r];
if(l==sdt) return dp[l][r]=dfs(l,r-1)+a[r]*(r-l+1);
if(r==sdt) return dp[l][r]=dfs(l+1,r)+a[l]*(r-l+1);
return dp[l][r]=max(dfs(l,r-1)+a[r]*(r-l+1),dfs(l+1,r)+a[l]*(r-l+1));
}
signed main()
{
int n=read(),t=read(),sum=0;
for(int i=1; i<=n; i++)
{
    c=read(),mx=read()-1,m=read(),sdt=read(),sum+=c;
    for(int j=1; j<=m; j++) a[j]=read();
    memset(dp,0,sizeof(dp));
    long long DP=dfs(1,m);
    //printf("> %lld\n",dp[1][m]);
    for(int j=0; j<min(sum,t+1); j++) ans[j][i&1]=-1000000000000000ll;
    for(int j=t; j>=sum; j--) ans[j][i&1]=ans[j-c][(i&1)^1]+DP;
    for(int j=1; j<=mx; mx-=j,j<<=1)
    {
        long long g=DP*j;
        int h=j*c;
        for(int k=t; k>=h; k--) ans[k][i&1]=max(ans[k][i&1],ans[k-h][i&1]+g);
    } 
    long long g=DP*mx;
    int h=mx*c;
    for(int k=t; k>=h; k--) ans[k][i&1]=max(ans[k][i&1],ans[k-h][i&1]+g); 
    for(int j=1; j<=t; j++) Ans=max(Ans,ans[j][i&1]);
}
printf("%lld\n",Ans);
return 0;
}