给定一个n个数的序列a,阿鱼先选择其中至多k个数删除,然后宇宇在剩下的数字中选至多x个数乘以−1,将剩余的数字加起来,阿鱼想要和尽可能大,宇宇想要和尽可能小,两者都非常聪明,所以选择的都是最佳决策,请问最后的结果为多少?用c++写出,不用vector
时间: 2024-10-06 15:03:09 浏览: 18
TC39xB-DS-v11.pdf
这个问题可以使用动态规划来解决,我们需要维护两个状态:dp1[i] 表示在前i个数中,阿鱼通过删除操作后,最大和;dp2[i] 表示在前i个数中,宇宇通过反转操作后,最小和。对于每个位置i,我们需要考虑三个情况:不删除,删除当前数,或删除当前数并反转它。
以下是C++代码实现,没有使用vector,而是用数组代替:
```cpp
#include <iostream>
using namespace std;
int a[n];
int dp1[n + 1], dp2[n + 1];
int main() {
int n, k, x;
cin >> n >> k >> x;
// 初始化dp1和dp2
dp1[0] = 0;
dp2[0] = a[0];
for (int i = 1; i <= n; ++i) {
dp1[i] = max(dp1[i - 1], dp1[i - 1] + a[i]);
dp2[i] = min(dp2[i - 1], dp2[i - 1] - a[i]);
}
// 双指针法求解
int ans1 = -INT_MAX, ans2 = INT_MAX; // 最大和和最小和初始设为负无穷和正无穷
int left = n, right = n;
while (left >= 0 && right >= 0) {
// 阿鱼可以选择删除一个数
if (right - left <= k) {
int temp1 = dp1[left] + dp2[right];
ans1 = max(ans1, temp1);
} else {
break;
}
// 宇宇可以选择反转一个数
if (left + 1 <= n && right + 1 <= n) {
int temp2 = dp1[left] + dp2[right] + a[left + 1] * 2;
ans2 = min(ans2, temp2);
} else {
break;
}
// 移动指针
left--;
right++;
}
cout << "最大和为:" << ans1 << endl;
cout << "最小和为:" << ans2 << endl;
return 0;
}
```
这段代码首先初始化了dp1和dp2,然后通过双指针方法不断尝试删除和反转操作,更新ans1和ans2。
阅读全文