SH10. 回文数组
描述
输入描述
输入数据由两行组成： 第一行包含一个正整数 L ，表示数组 a 的长度。 第二行包含 L 个正整数，表示数组 a 。 对于 40% 的数据： 1 < L <= 100 达成条件时需要插入的数字数量不多于 2 个。 对于 100% 的数据： 1 < L <= 1,000 0 < a[i] <= 1,000,000 达成条件时需要插入的数字数量没有限制。输出描述
输出一个整数，表示通过插入若干个正整数使数组 a 回文后，数组 a 的数字和的最小值。示例1
输入:
8 51 23 52 97 97 76 23 51
输出:
598
C++ 解法, 执行用时: 3ms, 内存消耗: 376KB, 提交时间: 2020-11-01
#include <algorithm>
#include <cstdio>
#include <numeric>
using namespace std;
const int N = 1005;
int solve();
//-----------INPUT-------------//
int n, nums[N];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", nums + i);
printf("%d\n", solve());
}
int forDp[2][N];
int solve() {
int *dp = forDp[0], *dp1 = forDp[1];
for (int i = n - 2; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] == nums[j]) dp[j] = dp1[j - 1];
else dp[j] = min(nums[i] + dp1[j], nums[j] + dp[j - 1]);
}
swap(dp, dp1);
}
return dp1[n - 1] + accumulate(nums, nums + n, 0);
}
C++ 解法, 执行用时: 4ms, 内存消耗: 376KB, 提交时间: 2020-12-23
#include <algorithm>
#include <cstdio>
#include <numeric>
using namespace std;
const int N = 1005;
int solve();
//-----------INPUT-------------//
int n, nums[N];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", nums + i);
printf("%d\n", solve());
}
int forDp[2][N];
int solve() {
int *dp = forDp[0], *dp1 = forDp[1];
for (int i = n - 2; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] == nums[j]) dp[j] = dp1[j - 1];
else dp[j] = min(nums[i] + dp1[j], nums[j] + dp[j - 1]);
}
swap(dp, dp1);
}
return dp1[n - 1] + accumulate(nums, nums + n, 0);
}
C++ 解法, 执行用时: 4ms, 内存消耗: 376KB, 提交时间: 2020-10-31
#include <algorithm>
#include <cstdio>
#include <numeric>
using namespace std;
const int N = 1005;
int solve();
//-----------INPUT-------------//
int n, nums[N];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", nums + i);
printf("%d\n", solve());
}
int forDp[2][N];
int solve() {
int *dp = forDp[0], *dp1 = forDp[1];
for (int i = n - 2; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] == nums[j]) dp[j] = dp1[j - 1];
else dp[j] = min(nums[i] + dp1[j], nums[j] + dp[j - 1]);
}
swap(dp, dp1);
}
return dp1[n - 1] + accumulate(nums, nums + n, 0);
}
C++ 解法, 执行用时: 4ms, 内存消耗: 492KB, 提交时间: 2020-10-31
#include <algorithm>
#include <cstdio>
#include <numeric>
using namespace std;
const int N = 1005;
int solve();
//-----------INPUT-------------//
int n, nums[N];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", nums + i);
printf("%d\n", solve());
}
int forDp[2][N];
int solve() {
int *dp = forDp[0], *dp1 = forDp[1];
for (int i = n - 2; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] == nums[j]) dp[j] = dp1[j - 1];
else dp[j] = min(nums[i] + dp1[j], nums[j] + dp[j - 1]);
}
swap(dp, dp1);
}
return dp1[n - 1] + accumulate(nums, nums + n, 0);
}
C++14 解法, 执行用时: 4ms, 内存消耗: 496KB, 提交时间: 2020-05-17
#include <algorithm>
#include <cstdio>
#include <numeric>
using namespace std;
const int N = 1005;
int solve();
//-----------INPUT-------------//
int n, nums[N];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", nums + i);
printf("%d\n", solve());
}
int forDp[2][N];
int solve() {
int *dp = forDp[0], *dp1 = forDp[1];
for (int i = n - 2; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] == nums[j]) dp[j] = dp1[j - 1];
else dp[j] = min(nums[i] + dp1[j], nums[j] + dp[j - 1]);
}
swap(dp, dp1);
}
return dp1[n - 1] + accumulate(nums, nums + n, 0);
}