一、
执行两次DP，第一次在任意位置把环断开成链，按照线性问题求解。
第二次通过适当的条件和赋值，保证计算的状态等价于把断开的位置强制相连。
Naptime POJ - 2228：
Goneril is a very sleep-deprived cow. Her day is partitioned into N (3 <= N <= 3,830) equal time periods but she can spend only B (2 <= B < N) not necessarily contiguous periods in bed. Due to her bovine hormone levels, each period has its own utility U_i (0 <= U_i <= 200,000), which is the amount of rest derived from sleeping during that period. These utility values are fixed and are independent of what Goneril chooses to do, including when she decides to be in bed.

With the help of her alarm clock, she can choose exactly which periods to spend in bed and which periods to spend doing more critical items such as writing papers or watching baseball. However, she can only get in or out of bed on the boundaries of a period.

She wants to choose her sleeping periods to maximize the sum of the utilities over the periods during which she is in bed. Unfortunately, every time she climbs in bed, she has to spend the first period falling asleep and gets no sleep utility from that period.

The periods wrap around in a circle; if Goneril spends both periods N and 1 in bed, then she does get sleep utility out of period 1.

What is the maximum total sleep utility Goneril can achieve?
Input

  • Line 1: Two space-separated integers: N and B

  • Lines 2…N+1: Line i+1 contains a single integer, U_i, between 0 and 200,000 inclusive
    Output
    The day is divided into 5 periods, with utilities 2, 0, 3, 1, 4 in that order. Goneril must pick 3 periods.
    Sample Input
    5 3
    2
    0
    3
    1
    4
    Sample Output
    6
    Hint
    INPUT DETAILS:

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

OUTPUT DETAILS:

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.

题意：
一天有N个小时，一头牛一天要睡B个小时，可以分段，但是在每段的第一个小时不获得体力，从第二个小时起，进入熟睡状态，其睡眠时间获得体力，其中今天的第N小时与第二天的第1小时相连。
我们在N和1之间断开，先求1–N线性dp，此时第一个小时不可能进入熟睡状态。强制连接N和1，此时只缺少了第一个小时也在熟睡状态的情况，若第一个小时也在熟睡状态，那么第N 个小时一定在休息。
会MLE ，数组滚动一下就好啦。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cmath>
#define ll long long
#define llu unsigned ll
using namespace std;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int maxn=3831;
const int mod=1e9+7;
int dp[2][maxn][2];
int wi[maxn];

int main(void)
{
    int N,b;
    while(scanf("%d%d",&N,&b)!=EOF)
    {
        for(int i=1;i<=N;i++)
            scanf("%d",&wi[i]);
        int ans=-inf;
        if(b==0)
        {
            printf("0\n");
            continue;
        }
        memset(dp,0x80,sizeof(dp));//-inf
        dp[1][0][0]=0,dp[1][1][1]=0;
        for(int i=2;i<=N;i++)
        {
            for(int j=0;j<=i&&j<=b;j++)
            {
                dp[i&1][j][0]=max(dp[(i-1)&1][j][0],dp[(i-1)&1][j][1]);
                if(j>=1)
                dp[i&1][j][1]=max(dp[(i-1)&1][j-1][0],dp[(i-1)&1][j-1][1]+wi[i]);
            }
        }
        ans=max(dp[N&1][b][0],dp[N&1][b][1]);
        memset(dp,0x80,sizeof(dp));
        dp[1][1][1]=wi[1];
        for(int i=2;i<=N;i++)
        {
            for(int j=0;j<=i&&j<=b;j++)
            {
                dp[i&1][j][0]=max(dp[(i-1)&1][j][0],dp[(i-1)&1][j][1]);
                if(j>=1)
                dp[i&1][j][1]=max(dp[(i-1)&1][j-1][0],dp[(i-1)&1][j-1][1]+wi[i]);
            }
        }
        ans=max(ans,dp[N&1][b][1]);

        printf("%d\n",ans);
    }
    return 0;
}

二、把环断开成链，然后复制一倍接在末尾：
ACWing
环路运输

在一条环形公路旁均匀地分布着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)。

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

输入格式
第一行包含一个整数N。

第二行包含N个整数A1~AN。

输出格式
输出一个整数，表示最大代价。

数据范围
1≤N≤1061≤N≤106,
1≤Ai≤1071≤Ai≤107
输入样例：
5
1 8 6 2 5
输出样例：
15
难度： 中等
时/空限制： 1s / 64MB
总通过数： 75
总尝试数： 166
来源： 《算法竞赛进阶指南》
我们在任意位置把环断开，复制一倍接在末尾，形成长为2N的直线公路，则上述问题可以转化为：
满足 1<=j＜i<=2N，并且 i - j<=N/2的哪两座仓库i，j之间运送货物，运送代价Ai + Aj + i - j最大。
枚举i，用单调 队列维护即可,就是使 Aj - j尽量大。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<deque>
#include<map>
#include<vector>
#include<cmath>
#define ll long long
#define llu unsigned ll
using namespace std;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int maxn=1001000;
const int mod=1e9+7;
int a[maxn*2];

int main(void)
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            a[i+n]=a[i];
        }

        int ans=-inf;
        deque<int>q;
        q.push_back(1);
        for(int i=2;i<=n*2;i++)
        {
            while(q.size()&&i-q.front()>n/2) q.pop_front();
            ans=max(ans,a[i]+a[q.front()]+i-q.front());
            while(q.size()&&a[i]-i>=a[q.back()]-q.back()) q.pop_back();
            q.push_back(i);
        }
        printf("%d\n",ans);
    }
    return 0;
}