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

uiii_ · 2025-12-02 17:31:43 · 题解

思路

AC 本题我们需要解决两个问题。一个是计算单关的最大得分，另一个则是计算总得分。

单关最大得分

依据题意，每次吃冰淇淋只能吃已有区间的两端，这一规则与区间 DP 相适应——每次扩展都是对当前区间左右的延伸。

用 dp_{l,r} 表示吃完区间 [l,r] 时的最大得分。状态转移方程如下——

• 初始化：dp_{c_i,c_i}\gets y_{c_i}（第一次吃指定的第 c_i 个冰淇淋）。
• 对于 dp_{l,r}：
  • 从 dp_{l+1,r} 向左扩展（最后吃 l）：dp_{l,r} \gets dp_{l+1,r}+len \cdot y_l
  • 从 dp_{l,r-1} 向右扩展（最后吃 r）：dp_{l,r}\gets dp_{l,r-1}+len \cdot y_r
  • 取两者的最大值即可。

代码实现时我们枚举区间长度 len 和左端点 l，那么右端点 r 为 (l+len-1)，再运用状态转移方程计算答案。

进行一次计算的时间复杂度为 \Theta(k^2)。

总得分

很显然这是一个多重背包问题，但多了一个想取第 i 个物品，必须先取第 i-1 个物品的限制条件。我们只需要先强制性取一个当前物品，再进行 dp 就可以保证当前物品至少取了一个。

注意为避免超时这里需要进行二进制拆分。不会的可以点这里。

时间复杂度为 \Theta(t \cdot \log m)。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=-1e18;
int n,t,s,m,k,c,y[510],v,dp[510][510],d[2][100010],ans=inf;
signed main(){
    scanf("%lld%lld",&n,&t);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld%lld%lld",&s,&m,&k,&c);
        for(int j=1;j<=k;j++){
            scanf("%lld",&y[j]);
        }//输入。 
        memset(dp,-0x3f,sizeof(dp));
        dp[c][c]=y[c];//初始化。 
        for(int len=2;len<=k;len++){
            for(int l=1;l+len-1<=k;l++){
                int r=l+len-1;
                dp[l][r]=max(dp[l+1][r]+len*y[l],dp[l][r-1]+len*y[r]);
            }
        }
        v=dp[1][k];//区间dp求单关最大得分。 
//s体力 m次数 v得分。 
        for(int j=0;j<=t;j++){
            d[i&1][j]=inf;
        } //初始化。 
        for(int j=t;j>=s;j--){
            d[i&1][j]=d[(i&1)^1][j-s]+v;
        } //先强制性取一次。 
        m--;
        for(int p=1;p<=m;p<<=1){
            for(int j=t;j>=s*p;j--){
                d[i&1][j]=max(d[i&1][j],d[i&1][j-s*p]+v*p);
            }
            m-=p;
        }
        if(m){
            for(int j=t;j>=s*m;j--){
                d[i&1][j]=max(d[i&1][j],d[i&1][j-s*m]+v*m);
            }
        }//多重背包。 
        for(int j=0;j<=t;j++){
            ans=max(ans,d[i&1][j]);
        }//更新答案。 
    }
    printf("%lld\n",ans);
    return 0;
} 

时间复杂度为 \Theta(n \cdot (k^2+t \cdot \log m))。

如有错误请指出。