DP.

Table of Contents

  1. Description
  2. Solution

Description

圆桌上摆放着$n$份食物，围成一圈，第$i$份食物所含热量为$c[i]$。

相邻两份食物之间坐着一个人，共有$n$个人。每个人有两种选择，吃自己左边或者右边的食物。如果两个人选择了同一份食物，这两个人会平分这份食物，每人获得一半的热量。

假如某个人改变自己的选择后（其他$n-1$个人的选择不变），可以使自己获得比原先更多的热量，那么这个人会不满意。

请你给每个人指定应该吃哪一份食物，使得所有人都能够满意。

Solution

观察到每个位置只有四种状态，左，右，两边，空。

我们可以枚举第一个位置的状态，向后递推做可达性DP。

口胡起来还是很简单啊转移方程很多很杂，要注意各种分类讨论和系数问题。

然后任取一组可行的状态构造解就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>

using namespace std;

const int maxn = 1e+6 + 6;

int n, a[maxn], f[maxn][4], nxt[maxn][4];
int tow[maxn], ans[maxn], ptr[maxn];

inline int rd() {
  register int x = 0, c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return x;
}
bool chk(int s) {
  memset(f, 0, sizeof f);
  f[1][s] = 1;
  for (int i = 2; i <= n; ++i) {
    if (f[i - 1][3] && a[i - 1] >= a[i] * 2) f[i][0] = 1, nxt[i][0] = 3;
    else if (f[i - 1][1] && a[i - 1] >= a[i]) f[i][0] = 1, nxt[i][0] = 1;
    if (f[i - 1][1] && a[i - 1] * 2 >= a[i]) f[i][1] = 1, nxt[i][1] = 1;
    else if (f[i - 1][3] && a[i - 1] >= a[i]) f[i][1] = 1, nxt[i][1] = 3;
    if (f[i - 1][2] && a[i - 1] <= a[i] * 2) f[i][2] = 1, nxt[i][2] = 2;
    else if (f[i - 1][0] && a[i - 1] <= a[i]) f[i][2] = 1, nxt[i][2] = 0;
    if (f[i - 1][0] && a[i - 1] * 2 <= a[i]) f[i][3] = 1, nxt[i][3] = 0;
    else if (f[i - 1][2] && a[i] >= a[i - 1]) f[i][3] = 1, nxt[i][3] = 2;
  }
  for (int i = 0; i < 4; ++i) 
    f[1][i] = 0, f[0][i] = f[n][i];
  a[0] = a[n];
  int i = 1;
  if (f[i - 1][3] && a[i - 1] >= a[i] * 2) f[i][0] = 1, nxt[i][0] = 3;
  else if (f[i - 1][1] && a[i - 1] >= a[i]) f[i][0] = 1, nxt[i][0] = 1;
  if (f[i - 1][1] && a[i - 1] * 2 >= a[i]) f[i][1] = 1, nxt[i][1] = 1;
  else if (f[i - 1][3] && a[i - 1] >= a[i]) f[i][1] = 1, nxt[i][1] = 3;
  if (f[i - 1][2] && a[i - 1] <= a[i] * 2) f[i][2] = 1, nxt[i][2] = 2;
  else if (f[i - 1][0] && a[i - 1] <= a[i]) f[i][2] = 1, nxt[i][2] = 0;
  if (f[i - 1][0] && a[i - 1] * 2 <= a[i]) f[i][3] = 1, nxt[i][3] = 0;
  else if (f[i - 1][2] && a[i] >= a[i - 1]) f[i][3] = 1, nxt[i][3] = 2;
  return f[1][s];
}

int main() {
  n = rd(); 
  for (int i = 1; i <= n; ++i) 
    a[i] = rd();
  bool sol = false; int pos = -1;
  for (int i = 0; i < 4; ++i) 
    if (chk(i)) {
      pos = i;
      sol = true; break;
    }
  if (!sol) puts("NIE");
  else {
    ptr[1] = pos;
    int sta = nxt[1][pos];
    for (int i = n; i > 1; --i) {
      ptr[i] = sta;
      sta = nxt[i][sta];
    }
    for (int i = 1; i <= n; ++i) {
      if (ptr[i] == 1 || ptr[i] == 3) ans[i] = i;
      if (ptr[i] == 2 || ptr[i] == 3) {
        ans[(i - 1) ? (i - 1) : n] = i;
      }
    }
    for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
  }
  return 0;
}