再卖菜

GitHub跳转原题关系图Canvas 关系图返回列表

记忆化判断相邻两个原价后的后缀可行性，再从小到大重建字典序最小序列。

OJ: shumeng

题目 ID: CSP201809D

难度:普及+/提高-

标签:动态规划记忆化搜索构造字典序

日期: 2026-07-31 16:21

目录

  1. 形式化题目
  2. 思路
    1. 朴素递归
    2. 记忆化后缀可行性
    3. 从小到大重建
    4. 样例状态转移
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

已知第二天价格序列 b1,b2,…,bnb_1, b_2, \dots, b_n，其中

b1=⌊a1+a22⌋,bi=⌊ai−1+ai+ai+13⌋ (2≤i≤n−1),bn=⌊an−1+an2⌋, b_1=\left\lfloor\frac{a_1+a_2}{2}\right\rfloor,\quad b_i=\left\lfloor\frac{a_{i-1}+a_i+a_{i+1}}{3}\right\rfloor\ (2\le i\le n-1),\quad b_n=\left\lfloor\frac{a_{n-1}+a_n}{2}\right\rfloor,

aia_i 均为正整数。求满足全部等式且字典序最小的序列 aa。

思路

朴素递归

把第一天每个价格看作一个选择。已确定 ai−1,aia_{i-1}, a_i 后，由

bi=⌊ai−1+ai+ai+13⌋ b_i=\left\lfloor\frac{a_{i-1}+a_i+a_{i+1}}3\right\rfloor

可知 ai+1a_{i+1} 只可能是 3bi−ai−1−ai3b_i-a_{i-1}-a_i、它加一、它加二这三个整数。小数据可以按这个三分支递归枚举，按字典序首先找到的完整方案就是答案。

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:41
 */
// brute.cpp：小数据暴力解，按字典序递归枚举每个下一天价格允许的三种原价。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 305;
const int MAX_VALUE = 305;

int n;
int second_price[MAXN]; // 第二天的已知菜价
int first_price[MAXN];  // 正在递归构造的第一天菜价

// 已经确定 a[position-1],a[position]，递归尝试 a[position+1] 的所有合法候选。
bool dfs(int position) {
    if (position == n) {
        return (first_price[n - 1] + first_price[n]) / 2 == second_price[n];
    }
    int lower = 3 * second_price[position] - first_price[position - 1] - first_price[position];
    for (int next = lower; next <= lower + 2; next++) {
        if (next < 1 || next >= MAX_VALUE) {
            continue;
        }
        first_price[position + 1] = next;
        if (dfs(position + 1)) {
            return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> second_price[i];
    }

    // 从小到大枚举 a[1],a[2]，按字典序找到的第一个完整方案就是答案。
    bool found = false;
    for (int first = 1; first < MAX_VALUE && !found; first++) {
        for (int second = 1; second < MAX_VALUE; second++) {
            if ((first + second) / 2 != second_price[1]) {
                continue;
            }
            first_price[1] = first;
            first_price[2] = second;
            if (n == 2 ? (first + second) / 2 == second_price[2] : dfs(2)) {
                found = true;
                break;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (i > 1) {
            cout << ' ';
        }
        cout << first_price[i];
    }
    cout << '\n';

    return 0;
}

记忆化后缀可行性

令 possible(i, x, y) 表示已经确定 ai−1=x, ai=ya_{i-1}=x,\ a_i=y 后，能否继续满足 bi,…,bnb_i,\dots,b_n。终点只需检查 (x+y)/2=bn(x+y)/2 = b_n；其余状态枚举上述至多三个正整数并记忆化，避免重复搜索。

所有原价格都不超过 302：中间位置相邻价格至少为 1，由三项和至多 3bi+2≤3023b_i+2 \le 302 可得上界，因此状态总数可控。

从小到大重建

先从小到大枚举满足端点平均值的 a1,a2a_1, a_2，取第一个 possible(2, a1, a2) 为真的二元组。之后每一步也按从小到大枚举三个候选并保留可行后缀，第一个选择必然使整个序列字典序最小。

样例状态转移

下表展示样例选出前缀 2, 2 后的构造。候选区间恰好连续三个整数，最小可行候选被写入下一列。

使用的第二天价格 已知相邻原价 下一项候选 选中值
b[2]=2 2,2 2,3,4 2
b[3]=1 2,2 -1,0,1 1
b[4]=3 2,1 6,7,8 6
b[5]=4 1,6 5,6,7 5

每个候选都先用 possible 判断是否能满足后续平均值；因此表中保留的最小值不是局部猜测，而是存在完整后缀的最小选择。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:41
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 305;
const int MAX_VALUE = 305;

int n;
int second_price[MAXN]; // 第二天的已知菜价 b[i]
int first_price[MAXN];  // 构造出来的第一天菜价 a[i]
signed char memo[MAXN][MAX_VALUE][MAX_VALUE]; // memo[i][x][y]：已定 a[i-1]=x,a[i]=y 时后缀是否可行

// 已经确定 a[position-1]=previous、a[position]=current，判断能否继续填出
// a[position+1..n]，使 b[position..n] 全部满足。
bool possible(int position, int previous, int current) {
    if (position == n) {
        return (previous + current) / 2 == second_price[n];
    }
    signed char &result = memo[position][previous][current];
    if (result != -1) {
        return result;
    }

    // 由 b[position] = floor((a[i-1]+a[i]+a[i+1])/3) 反解：
    // 下一个原价只可能是 lower、lower+1、lower+2 三个连续整数。
    int lower = 3 * second_price[position] - previous - current;
    for (int next = lower; next <= lower + 2; next++) {
        if (next >= 1 && next < MAX_VALUE && possible(position + 1, current, next)) {
            result = 1;
            return true;
        }
    }
    result = 0;
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> second_price[i];
    }
    memset(memo, -1, sizeof(memo));

    // 从小到大枚举 a[1],a[2]，找第一个能推出完整可行方案的一对。
    bool found = false;
    for (int first = 1; first < MAX_VALUE && !found; first++) {
        for (int second = 1; second < MAX_VALUE; second++) {
            if ((first + second) / 2 != second_price[1]) {
                continue;
            }
            if (n == 2) {
                if ((first + second) / 2 == second_price[2]) {
                    first_price[1] = first;
                    first_price[2] = second;
                    found = true;
                    break;
                }
            } else if (possible(2, first, second)) {
                first_price[1] = first;
                first_price[2] = second;
                found = true;
                break;
            }
        }
    }

    // 每个位置从小到大尝试三个候选，第一个存在完整后缀的就是字典序最优选择。
    for (int position = 2; position <= n - 1; position++) {
        int lower = 3 * second_price[position]
                - first_price[position - 1] - first_price[position];
        for (int next = lower; next <= lower + 2; next++) {
            if (next >= 1 && next < MAX_VALUE
                    && possible(position + 1, first_price[position], next)) {
                first_price[position + 1] = next;
                break;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (i > 1) {
            cout << ' ';
        }
        cout << first_price[i];
    }
    cout << '\n';

    return 0;
}

复杂度

状态为位置与两个相邻原价，原价范围至多 302。时间复杂度 O(n⋅3022)O(n \cdot 302^2)，每个状态只检查 3 个后继；空间复杂度同为 O(n⋅3022)O(n \cdot 302^2)，约 28MB。

总结

逆向平均不需要枚举整个价格序列。局部等式把下一个值压缩为三个选择，记忆化后缀可行性负责避免贪心走进死路；在每个位置优先尝试更小候选即可得到字典序最小解。