NAPTIME - Naptime

题面翻译

在某个星球上，一天由 $n$ 小时构成。我们称 $0 \sim 1$ 点为第一个小时，$1 \sim 2$ 点为第二个小时，以此类推。在第 $i$ 个小时睡觉能恢复 $U_i$ 点体力。在这座星球上住着一头牛，它每天要休息 $B$ 个小时，它休息的这 $B$ 个小时可以不连续，可以分成若干段，但是在每一段的第一个小时不能恢复体力，从第二个小时开始才可以恢复体力。为了身体健康，这头牛希望遵循生物钟，每天采用相同的睡觉计划。另外，因为时间是连续的，每天的第 $n$ 个小时与下一天的第一个小时是相连的，这头牛只需要在 $n$ 个小时内休息 $B$ 个小时就够了。请你给这头牛安排一个任务计划，使得它每天恢复的体力最多。

输入格式：第一行一个整数 $T$ 表示有 $T$ 组测试数据对于每一组测试数据，第一行为两个整数 $n$ 与 $B$，接下来 $n$ 行每行一个整数 $U_i$。$2 \le B < N \le 3830 , 0 \le Ui \le 2 \times 10^5$。

输出格式：对于每组输入数据，对应一行输出一个整数，表示答案。（注意：两组输出之间没有空行）

样例 #1

样例输入 #1

样例输出 #1

6

Input/Output details:
The day is divided into 5 periods, with utilities 2, 0, 3, 1, 4 in that 
order. Goneril must pick 3 periods.

Goneril can get total utility 6 by being in bed during periods 4,
5, and 1, with utilities 0 [getting to sleep], 4, and 2
respectively.

环上dp的做法

我们将环切成一个链之后，倍长该链做dp即可做到从每一位出发，可参考P1880石子合并。
我们抢先将环切成一条链，然后枚举断点的状态，即为这道SP283。

条件

n时间内总共睡 b 小时。
每一段睡觉区间第一段时间不参与贡献。

这是一个环上dp

我们考虑枚举点状态

dp[i][j][1]表示第i时刻睡了j小时，1表示睡了，同理0表示没睡

推理得到dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1])，因为你现在没睡，上一个时刻睡了也没有贡献的

同理，又可以推理得到dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j-1][1]+a[i])

n时刻没睡dp[1][0][0]=0,dp[1][1][1]=0;

n时刻睡了dp[1][0][0]=0,dp[1][1][1]=a[1];

#include<bits/stdc++.h>
using ll=long long;
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
const int N=3840;
int t;
int n,b;
int ans=-1;
int dp[N][N][2];
int a[N];
signed main()
{
int t=1;
    cin>>t;
    while(t--)
    {
        cin>>n>>b;
        rep(i,1,n)
        {
            cin>>a[i];
        }
        memset(dp,-0x3f,sizeof dp);
        dp[1][0][0]=0;
        dp[1][1][1]=0;
        rep(i,2,n)
        {
            rep(j,0,min(i,b))
            {
                dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);
                dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j-1][1]+a[i]);
            }
        }
        ans=dp[n][b][0];
        memset(dp,-0x3f,sizeof dp);
        dp[1][0][0]=0;
        dp[1][1][1]=a[1];
        rep(i,2,n)
        {
            rep(j,0,min(i,b))
            {
                dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);
                dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j-1][1]+a[i]);
            }
        }
     ans=max(ans,dp[n][b][1]);
        cout<<ans<<'\n';    
    }
}

见下双倍经验：

[USACO05JAN] Naptime G

题目描述

贝茜是一只非常缺觉的奶牛．她的一天被平均分割成 $N$ 段（$3 \leq N \leq 3830$），但是她要用其中的 $B$ 段时间（$2 \leq B \lt N$）睡觉。每段时间都有一个效用值 $U_i$（$0 \leq U_i \leq 2 \times 10^5$），只有当她睡觉的时候，才会发挥效用。

有了闹钟的帮助，贝茜可以选择任意的时间入睡，当然，她只能在时间划分的边界处入睡、醒来。

贝茜想使所有睡觉效用的总和最大。不幸的是，每一段睡眠的第一个时间阶段都是“入睡”阶段，而旦不记入效用值。

时间阶段是不断循环的圆（一天一天是循环的嘛），假如贝茜在时间 $N$ 和时间 $1$ 睡觉，那么她将得到时间 $1$ 的效用值。

输入格式

第一行两个整数 $N,B$。

接下来 $N$ 行，每行一个整数，表示第 $i$ 个时段的效用值。

输出格式

输出最大效用值。

样例 #1

样例输入 #1

样例输出 #1

提示

从第 $4$ 个时段入睡，到第 $1$ 个时段结束醒来。

环路运输

在一条环形公路旁均匀地分布着$N$座仓库，编号为$1~N$，编号为$ i$ 的仓库与编号为 $j$ 的仓库之间的距离定义为 $dist(i,j)=min⁡(|i-j|,N-|i-j|)$，也就是逆时针或顺时针从$ i $到 $j$ 中较近的一种。

每座仓库都存有货物，其中编号为 $i$ 的仓库库存量为$ Ai$。

在$ i$ 和 $j$ 两座仓库之间运送货物需要的代价为 $Ai+Aj+dist(i,j)$。

求在哪两座仓库之间运送货物需要的代价最大。

样例

in:
5
1 8 6 2 5

out:
5

算法1: 枚举(60pts) 枚举任意两个仓库$i、j$，计算代价并更新$ans$。对于每个$i$，为避免重复扫描只需枚举$1 <= j < i$，因为$j > i$的情况在$i$向后枚举时会扫到。

时间复杂度 O($n^2$)

for(int i = 1; i <= n; i++) {
        cin>>a[i];
        for(int j = 1; j < i; j++)
            ans = max(ans, a[i]+a[j]+dis(i,j) );
    }

算法2 破环成链&朴素DP(60pts) 像区间DP一样，在任意位置（如$1$和$n$之间）把环断开，复制一倍接在末尾，$a[i+n] = a[i]$。对于原来环形公路上的任意两座仓库$i$、$j$，若$i-j <= n>>1$，则在新的直线公路上仍对应为$i$、$j$；若$i-j > n>>1$，则在直线公路上对应为$i$、$j+n$。综上：原问题可化为，长度为2n的直线公路上，在满足$1 <= j < i <= 2n$ && $i-j <= n>>1$的仓库$i$、$j$见运送货物，使代价$a[i]+a[j]+i-j$最大。

时间复杂度同上

考虑优化，单调队列上！！

思考公式转化

在计算代价公式时，如果能够将公式中的同类项合并，比如将 $ A_i $ 和 $ i $ 合并起来考虑，同时将 $ A_j $ 和 $ j $ 合并起来考虑，每次枚举 $ i $ 时，$ A_i $ 和 $ i $ 都是定值，这样只需要维护一个最值就可以求解答案。

然而，由于公式中的距离 $ (i, j) $ 包含绝对值符号，无法直接将 $ i $ 和 $ j $ 分离计算。为了解决这个问题，可以通过以下步骤转化公式。

定义最短距离公式：

原公式中的距离可以表示为：
$ (i, j) = (|i - j|, N - |i - j|) $

这里的距离定义为环形结构上的最短距离。观察到：
- 最短距离一定小于等于周长的一半（即 $ N/2 $）。
进一步转换：

去掉绝对值并考虑两种情况，公式可以化简为： $ (i, j) =
\[\begin{cases} i - j & \text{当 } |i - j| \leq N/2 \\ N - (i - j) & \text{否则} \end{cases}\]
$
观察区间范围：

在实际计算中，$ j $ 始终处于一个长度为 $ N/2 $ 的滑动区间内。因此，可以借助滑动窗口来优化计算。

单调队列的作用：
- 单调队列维护当前滑动窗口内的元素。
- 队列中的元素按递减（或递增）顺序排列，方便随时获取最大值（或最小值）。
优化步骤：
- 遍历 $ i $，维护一个滑动窗口，其范围为 $ [i - N/2, i] $。
- 每次根据单调队列获取当前窗口的最值，更新结果。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2000010;
int q[N];
LL a[N];
int n;

int main()
{
    cin>>n;
    for(int i = 1;i <= n;i ++)
    {
        cin>>a[i];
        a[i + n] = a[i];//破环成链
    }
    LL res = 0;
    int hh = 0,tt = -1;
    for(int i = 1;i <= n * 2;i ++)
    {
        if(hh <= tt && i - q[hh] > n / 2) hh ++;
        //超出N/2的范围了就直接跳
        if(i >= n + 1) res = max(res,a[i] + a[q[hh]] + i - q[hh]);
        while(hh <= tt && a[q[tt]] - q[tt] <= a[i] - i) tt --;
        //比他大也直接减
        q[++ tt] = i;
        //最后记录
    }
    cout<<ans;
    return 0;
}