题目地址：洛谷：【P3584】[POI2015]LAS – 洛谷、BZOJ：Problem 3749. — [POI2015]Łasuchy

题目描述

圆桌上摆放着n份食物，围成一圈，第i份食物所含热量为c[i]。 相邻两份食物之间坐着一个人，共有n个人。每个人有两种选择，吃自己左边或者右边的食物。如果两个人选择了同一份食物，这两个人会平分这份食物，每人获得一半的热量。 假如某个人改变自己的选择后（其他n-1个人的选择不变），可以使自己获得比原先更多的热量，那么这个人会不满意。 请你给每个人指定应该吃哪一份食物，使得所有人都能够满意。

输入输出格式

输入格式：
第一行一个整数n(2<=n<=1000000)，表示食物的数量（即人数）。食物和人都从1~n编号。
第二行包含n个整数c[1],c[2],…,c[n] (1<=c[i]<=10^9)。
假设第i个人(1<=i<n)左边是第i份食物，右边是第i+1份食物；而第n个人左边是第n份食物，右边是第1份食物。

输出格式：
如果不存在这样的方案，仅输出一行NIE。
如果存在这样的方案，输出一行共n个整数，第i个整数表示第i个人选择的食物的编号。如果有多组这样的方案，输出任意一个即可。

输入输出样例

输入样例#1：

5
5 3 7 2 9

输出样例#1：

2 3 3 5 1 

题解

是一个动态规划的判定问题。我们可以枚举第一个食物被左边/右边/两边/没被吃的情况，然后通过递推获得后面的食物的某个状态的可行性。
例如，当前一个食物被左边的人吃了，显然当前食物是必须让当前的左边的人吃掉的，而枚举剩下的情况，就是右边的人吃不吃，从而判断左边的人吃当前食物对他来说是否是最优的。
我们可以在DP的过程中记下上一个状态，在输出方案的时候倒推统计每个人吃的是什么食物，这样就可以输出方案了。
这个DP的复杂度是O(n)的。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 1000005;

// 1: left 2: right 3: both 4: neither
int n, dp[MAXN][5];
LL c[MAXN];

inline bool caldp(int s) {
    memset(dp, 0, sizeof(dp));
    dp[1][s] = 1;
    for(int i = 2; i <= n + 1; i++) {
        if(dp[i - 1][1] && c[i - 1] <= c[i] * 2) dp[i][1] = 1;
        if(dp[i - 1][1] && c[i - 1] <= c[i]) dp[i][3] = 1;
        if(dp[i - 1][2] && c[i - 1] * 2 >= c[i]) dp[i][2] = 2;
        if(dp[i - 1][2] && c[i - 1] >= c[i]) dp[i][4] = 2;
        if(dp[i - 1][3] && c[i - 1] >= c[i]) dp[i][2] = 3;
        if(dp[i - 1][3] && c[i - 1] >= c[i] * 2) dp[i][4] = 3;
        if(dp[i - 1][4] && c[i - 1] <= c[i]) dp[i][1] = 4;
        if(dp[i - 1][4] && c[i - 1] * 2 <= c[i]) dp[i][3] = 4;
    }
    return dp[n + 1][s];
}

int ans[MAXN];

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        c[i] = readint();
    }
    c[n + 1] = c[1];
    bool success = false;
    for(int i = 1; i <= 4; i++) {
        if(caldp(i)) {
            int type = i;
            for(int i = n + 1; i >= 1; i--) {
                if(type == 1) ans[i - 1] = (i - 1) % n + 1;
                if(type == 2) ans[i] = (i - 1) % n + 1;
                if(type == 3) ans[i - 1] = ans[i] = (i - 1) % n + 1;
                type = dp[i][type];
            }
            for(int i = 1; i <= n; i++) {
                printf("%d ", ans[i]);
            }
            return 0;
        }
    }
    puts("NIE");
    return 0;
}