HDU - 6984 Tree Planting 题解

DimStar
  2026-03-05 18:02:43 2026-03-05 18:02:43 创建   2026-03-05 18:05:37 2026-03-05 18:05:37 更新      1.3k 字  6 分钟  

Source

【专题训练】分块、根号分治与整除分块 - S

题目大意

给定 ，和一个长度为 的正整数数组 ，你可以选择其中的一些元素，要求不能选相邻元素，也不能同时选 和 ，一种选择方案的权值是方案中所有被选 之和，求所有合法方案的权值之和。

保证 ，。

Solution

注意到统计答案只能往 DP 方向去想，但是不能同时选 和 这个限制很烦，要想转移就必须知道前面选择的具体方案，人话就是要用二进制状态压缩来做。但是 又太大，直接 肯定不行。

咋办嘞，发现 比较小的时候可以直接做，然后这个 的范围 就很有趣， 大概是 ，是一个很诱人的数字，勾引你去想根号分治加状压 DP。显然 比较大的时候， 比较小，考虑在这个维度上做状压 DP。发现假如把原来的 数组变成一个 的矩阵，那么不能选相邻元素和不能选同一列的元素，这就变成了在一个 行 列的矩阵中选元素，要求不能选相邻的元素，在这个矩阵的两侧还有一些边界条件，即上一行的末尾和下一行的开头不能同时选。

先前面提到 比较小的时候可以直接做，就是在矩阵中逐行 DP，而反之， 比较大的时候就可以逐列 DP，但是注意到我们需要记录边界条件（第一列），转移时需要考虑下一列，每一列状态数是 ，但是由于不能选相邻元素，所以实际状态数会小很多，最多 （ 是斐波那契数列）。

然后我们需要预处理出每一列从状态 可以转移到那些状态 （以减小常数），以及转移贡献多少权值。然后需要枚举首列，接着 DP 转移到最后一列，枚举末列，若首列和末列不冲突则累加答案。

时间复杂度

第一种 DP 时间复杂度 。

第二种 DP 时间复杂度 ，但是有常数优化。

实际阈值取 跑得比较快，最后跑了 1809 ms。

Code

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include <bits/stdc++.h>
#define nmf(i, s, e) for (int i = s; i <= e; i++)
#define ref(i, s, e) for (int i = s; i >= e; i--)
namespace FastIO
{
    template <typename T>
    inline void read(T &x)
    {
        short neg = 1;
        char ch;
        while (ch = getchar(), !isdigit(ch))
            if (ch == '-')
                neg = -1;
        x = ch - '0';
        while (ch = getchar(), isdigit(ch))
            x = (x << 3) + (x << 1) + (ch ^ '0');
        x *= neg;
    }
    template <typename T, typename... Args>
    inline void read(T &x, Args &...args)
    {
        read(x);
        read(args...);
    }
    template <typename T>
    inline void read(T *begin, T *end)
    {
        unsigned len = end - begin;
        for (unsigned i = 0; i < len; i++)
            read(*(begin + i));
    }
    template <typename T>
    inline void write(T x)
    {
        if (x < 0)
            putchar('-'), x = -x;
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
    template <typename T, typename... Args>
    inline void write(T x, Args... args)
    {
        write(x);
        putchar(' ');
        write(args...);
    }
    template <typename T>
    inline void write(T *begin, T *end)
    {
        unsigned len = end - begin;
        for (unsigned i = 0; i < len; i++)
            write(*(begin + i)), putchar(' ');
    }
}
using namespace FastIO;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int mod = 1e9 + 7;
void modadd(int &x, const int &y)
{
    x += y;
    if (x >= mod)
        x -= mod;
}
int n, k;
int w[305];
namespace solve1
{
    int st[500005], id[33550336 + 4101];
    int f[2][(1 << 25) + 5];
    void solve()
    {
        int statecnt = 0;
        nmf(i, 1, (1 << k) - 1)
        {
            id[i] = 0;
            if (!(i & (i << 1)))
                st[++statecnt] = i, id[i] = statecnt;
        }
        int op = 0;
        memset(f[op], 0, (statecnt + 2) * sizeof(int));
        f[op][0] = 1;
        nmf(i, 1, n)
        {
            memset(f[op ^ 1], 0, (statecnt + 2) * sizeof(int));
            nmf(j, 0, statecnt)
            {
                int s = st[j];
                if (f[op][j])
                {
                    int t = ((s << 1) | (1 << k)) ^ (1 << k); // 去除溢出的首位
                    modadd(f[op ^ 1][id[t]], f[op][j]);
                    if (((~t) & 2) && (((~s) & (1 << (k - 1))))) // 确保满足条件
                        modadd(f[op ^ 1][id[t | 1]], 1ll * f[op][j] * w[i] % mod);
                }
            }
            op ^= 1;
        }
        int ans = 0;
        nmf(j, 0, statecnt) modadd(ans, f[op][j]);
        modadd(ans, mod - 1);
        write(ans), putchar('\n');
        return;
    }
}
namespace solve2
{
    int st[1005], id[4100];
    int f[2][1005], val[305][1005];
    int nxt[1005][1005]; // nxt[0] 存储可行的下一个状态数量
    void solve()
    {
        int h = n / k + 1, ans = 0;
        int statecnt = 0;
        nmf(i, 1, (1 << h) - 1)
        {
            id[i] = 0;
            if (!(i & (i << 1)))
                st[++statecnt] = i, id[i] = statecnt;
        }
        nmf(i, 1, k)
        {
            memset(val[i], 0, (statecnt + 2) * sizeof(int));
            nmf(j, 0, statecnt)
            {
                int s = st[j];
                if ((h - 1) * k + i > n /*这一格不存在*/ && (s & (1 << (h - 1))))
                    continue;
                val[i][j] = 1;
                nmf(Cyrene, 1, h) if (s & (1 << (Cyrene - 1)))
                    val[i][j] = 1ll * val[i][j] * w[(Cyrene - 1) * k + i] % mod;
            }
        }
        nmf(i, 0, statecnt)
        {
            nxt[i][0] = 0;
            nmf(j, 0, statecnt)
            {
                if (!(st[i] & st[j]))
                    nxt[i][++nxt[i][0]] = j;
            }
        }
        nmf(head, 0, statecnt)
        {
            int s = st[head];
            if ((h - 1) * k + 1 > n /*这一格不存在*/ && (s & (1 << (h - 1))))
                continue;
            int op = 0;
            memset(f[op], 0, (statecnt + 2) * sizeof(int));
            f[op][head] = val[1][head];
            nmf(i, 1, k - 1)
            {
                memset(f[op ^ 1], 0, (statecnt + 2) * sizeof(int));
                nmf(j, 0, statecnt) if (f[op][j])
                    nmf(o, 1, nxt[j][0])
                        modadd(f[op ^ 1][nxt[j][o]], 1ll * f[op][j] * val[i + 1][nxt[j][o]] % mod);
                op ^= 1;
            }
            nmf(i, 0, statecnt) if (!((st[i] << 1) & s))
                modadd(ans, f[op][i]);
        }
        modadd(ans, mod - 1);
        write(ans), putchar('\n');
    }
}
void solve()
{
    read(n, k);
    read(w + 1, w + 1 + n);
    int B = min(int(sqrt(2 * n) + 1), n);
    if (k <= B)
        solve1::solve();
    else
        solve2::solve();
    return;
}
signed main()
{
    int T = 1;
    read(T);
    while (T--)
        solve();
    return 0;
}
  • 标题: HDU - 6984 Tree Planting 题解
  • 作者: DimStar
  • 创建于 : 2026-03-05 18:02:43
  • 更新于 : 2026-03-05 18:05:37
  • 链接: https://dimstar-zhang.github.io/2026/03/05/HDU6984-Tree-Planting-题解/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
目录
HDU - 6984 Tree Planting 题解
  1. Source
  2. 题目大意
  3. Solution
  4. 时间复杂度
  5. Code