AcWing 3503. 数组划分(用前缀和剪枝)
可以设想一开始所有元素都已经在一个和较大的数组中,这样只需要dfs数组的0~i-1元素,选不选择把它抽出来放在较小的数组中。
关键优化:构建前缀和数组,从后向前dfs原数组。因为我们当前dfs中选择出来的元素都是放在较小的数组中,所以如果接下来k个元素之和越来越小,(也就是即使全选,两个数组和的差距也越来越大)时,这样就不再需要遍历接下来不选0~k个元素的情况了。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, a[N], sum[N];
int dis = 0x3f3f3f3f, ans; // 两数组和的距离 较小的那个数组和
bool flag;
void dfs(int cur, int idx) {
if (flag) return;
if (cur > sum[n - 1] / 2) return; // 只寻找较小的数组和,另外一个一定能表示为sum[n - 1] - cur
if (idx == -1) {
int d = sum[n - 1] - 2 * cur;
if (d < dis) {
dis = d;
ans = cur;
if (dis == 0 || dis == 1) // 如果已经找到不可能再优化的结果,直接返回
flag = true;
}
return;
}
dfs(cur + a[idx], idx - 1);
// 当接下来全选时,选的数组和为cur + sum[idx - 1],如果全选都导致dis越来越大,就不用遍历了
int next_max = cur + sum[idx - 1];
if (!(next_max < sum[n - 1] / 2 && sum[n - 1] - 2 * (next_max) > dis))
dfs(cur, idx - 1);
// else
// cout << "next_max " << next_max << " " << sum[n - 1] / 2 << endl;
}
int main() {
int t;
while (cin >> t) a[n++] = t;
sort(a, a + n); // 从小到大排序可以将时间从515ms降到17ms
sum[0] = a[0];
for (int i = 1; i < n; i++)
sum[i] = a[i] + sum[i - 1]; // 前缀和
dfs(0, n - 1); // 从后向前遍历每个元素,方便使用前缀和预判剪枝
cout << sum[n - 1] - ans << " " << ans;
}
求问佬,像你的代码中描述的那样,用cin真能成功读取数组吗?
当然可以,这样写没啥问题
tql,
好奇1000个数的范围,为什么不是先想dp呢,我觉得跟leetcode上有一题石子游戏很像,就用dp了
好问题,没先想dp是因为我lc刷的少)最近做到那题了,空了看看
刚完全背包写完超时 sum太大了 动态数组遍历完就爆了