补充一种非贪心的另类 dp 解法。
根据题目，不难发现只有 的数字是有要求的，需要和为 ，而其它地方只需要把剩下的数填进去就行了。因此不妨令 ，那么就需要在 当中选择 个数加起来等于 。
于是，我们便可以将这 个数看成 个物品，构造出 01 背包。令 表示为在 当中选择了 个不同的数，加起来能否等于 ，那么这个数可以由 个数转移来，便是
但是这个办法需要开 的数组，空间复杂度 ，而本题 ，自然会超出内存限制。但是，我们可以通过压数组的手段来讲第一维去掉。因为 只会依赖 ，而 这个维度也只会访问 ，因此我们只需要将 倒序枚举即可。
这样做空间能够得到有效的优化，但时间复杂度仍然是 。考虑优化时间，比如当答案 已经计算出来了的时候，就退出 dp。但是最有效的方法还是直接在循环外面判断解是否合法，如果 加起来都比 大或者 加起来都比 要小，那么肯定是满足不了条件的，因此直接输出无解。
注意这题需要输出答案，因此 dp 需要记录前驱状态。但是实际上并不用开两个数组，只需要记录当前状态是加了多少就行了。一秒半大常数过题。
#include <iostream>
#include <set>
using namespace std;
const int kMaxN = 505, kMaxS = kMaxN * (kMaxN + 1) / 2;
int dp[kMaxN][kMaxS], f[kMaxN], p, t, n, m, l, r, s;
set<int> st;
int main() {
for (cin >> t; t; t--) {
cin >> n >> l >> r >> s;
m = r - l + 1, p = 1;
if ((n - m + 1 + n) * m / 2 < s || (1 + m) * m / 2 > s) {
cout << "-1\n";
continue;
}
fill(f + 1, f + n + 1, 0);
for (int i = 1; i <= m; i++) {
for (int j = i; j <= s; j++) {
dp[i][j] = 0;
}
}
dp[0][0] = 1, st.clear();
for (int i = 1; i <= n; i++) {
if (dp[m][s]) {
break;
}
for (int j = min(m, i); j >= 1; j--) {
for (int k = i; k <= min(s, i * (i + 1) / 2); k++) {
dp[j - 1][k - i] && !dp[j][k] && (dp[j][k] = i);
}
}
}
for (int i = 1; i <= n; i++) {
st.insert(i);
}
for (int i = m, j = s; i; j -= dp[i][j], i--) {
f[l + i - 1] = dp[i][j];
st.erase(dp[i][j]);
}
for (int i = 1; i <= n; i++) {
if (f[i]) {
cout << f[i] << ' ';
} else {
cout << *st.begin() << ' ';
st.erase(st.begin());
}
}
cout << '\n';
}
return 0;
}