在题解里我会放两版代码，可以看一下我最后卡常卡过去做出的一些优化
先讲题目本身好了
两数之和 s 最小是2（2个1），最大是2000（2个1000），数不是特别大，我们可以枚举它
我们枚举每一个可能的 s，分别求出在 固定和等于 s 的条件下，能够选出的最长对称子序列的长度，最后取所有 s 中的最大值。
然后我们发现这题可以用区间dp来解，设 dp[l][r] 表示在原数组的下标区间 [l,r] 内，能够选出的、满足所有配对和等于 s 的最长子序列的长度。
对于区间 [l,r] 的状态转移共三种情况：
1.取两端的元素配对
如果 a[l] + a[r] = s，那么我们可以将这两个元素作为子序列的最外一对，再配上区间 [l+1,r−1] 内能选出的最优子序列（它本身也满足所有配对和等于 s）。
所以转移方程为 dp[l][r] = max(dp[l][r], dp[l+1][r-1])（前提区间 [l+1, r−1]不是空集，即至少有一个元素，r-1 >= l+1）
2.不取左端点
子序列完全由区间 [l+1, r] 构成：
所以转移方程为 dp[l][r] = max(dp[l][r], dp[l+1][r])
3.不取右端点
子序列完全由区间 [l, r-1] 构成：
所以转移方程为 dp[l][r] = max(dp[l][r], dp[l][r-1])
然后还有一个边界情况要考虑
当 l = r 的时候，区间里只有一个元素a[l]，如果有2 * a[l] = s的话，它自己也是合法的对称子序列
所以初始化的时候，若2 * a[i] = s的话，那么dp[i][i]要初始化为1，其他情况时，dp数组初始化都是0
然后我们按区间长度从小到大计算，长度从1到n，每个区间从更短的区间处转移过来
我们最后的答案就是dp[1][n]
然后就写出来了现在这个初版代码
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << '\n';
// #define int long long
#define ctz __builtin_ctzll // 返回二进制表示中末尾连续0的个数
#define clz __builtin_clzll // 返回二进驻表示中先导0的个数
#define count1 __builtin_popcountll // 返回二进制表示中1的个数
// 上面仨不是ll的时候记得调整
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int hash_base = 881;
const int N = 1e6 + 10000;
const double EPS = 1e-8;
const ll MOD = 676767677;
// const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
ll dirr[8][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
void LiangBaiKai()
{
}
void Aiden()
{
ll m, n, k, sum = 0, ans = 0, num = 0, mi = INF, ma = -INF, cnt = 0, x, y, z, len, t, l, r, cur;
string s1, s2;
cin >> n;
vector<ll> a(n + 1);
for (ll i = 1; i <= n;i++)
cin >> a[i];
ans = 1;
for (ll s = 2; s <= 2000;s++)
{
vector dp(n + 1, vector<ll>(n + 1));
for (ll i = 1; i <= n;i++)
{
if (2 * a[i] == s)
dp[i][i] = 1;
}
for (ll len = 2; len <= n;len++)
{
for (ll l = 1; l + len - 1 <= n;l++)
{
r = l + len - 1;
if (a[l] + a[r] == s)
{
ll in = (r - l >= 2) ? dp[l + 1][r - 1] : 0;
dp[l][r] = max(dp[l][r], in + 2);
}
dp[l][r] = max(dp[l][r], dp[l + 1][r]);
dp[l][r] = max(dp[l][r], dp[l][r - 1]);
}
}
ans = max(ans, dp[1][n]);
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
LiangBaiKai();
int _ = 1;
cin >> _;
while (_--)
Aiden();
return 0;
}
然后果不其然t了，这个时候我们极限运算次数是 2000 * 500 * 500 * 5 = 2.5e9 这显然是要t的，然后蒟蒻的主包想了很久怎么卡过去，下面是我做出亿些优化
1.统计了所有a[i]中出现的最大值max，这样我们的第一层循环就不用跑满 2000，从 2 到 2 * max 即可
2.跑一个 O(n^2) 的双重循环，用 vis 数组记录可能出现的两数之和 s 会有哪些值，跑循环的时候如果 vis[x] = 0 就直接 continue 掉，因为压根没有 2 个数的和会是 x
3.统计 ans 的时候，由于 ans 的最大值肯定也只有 n ，所以如果我们在循环的过程中发现 ans 已经为 n 了，就直接 break 掉，进行可行性剪枝
4.改用静态的 dp 数组，不进行 O(n ^ 2) 的 dp 数组初始化，只初始化对角线 dp[i][i] 的值，其余状态通过直接赋值覆盖掉，不取旧值了，拿一个 best 变量来计算最优情况以后直接给 dp[l][r] 赋值为 best （这个优化非常重要！！！是目前所有优化里最能显著优化时间的，因为把一次 O(n ^ 2) 优化为了 O(n) ）
5.快读好像有可能也对这题有帮助，我没测试，但是好像看到有群友用完快读直接从 tle 变成 1000ms 左右了，有点神秘了，数据量明明很小啊
最后修改完以后的代码如下：
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << '\n';
// #define int long long
#define ctz __builtin_ctzll // 返回二进制表示中末尾连续0的个数
#define clz __builtin_clzll // 返回二进驻表示中先导0的个数
#define count1 __builtin_popcountll // 返回二进制表示中1的个数
// 上面仨不是ll的时候记得调整
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int hash_base = 881;
const int N = 1e6 + 10000;
const double EPS = 1e-8;
const ll MOD = 676767677;
// const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
ll dirr[8][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
void LiangBaiKai()
{
}
bool vis[2005];
ll dp[505][505]; // 用静态数组
void Aiden()
{
ll m, n, k, sum = 0, ans = 0, num = 0, mi = INF, ma = -INF, cnt = 0, x, y, z, len, t, l, r, cur;
string s1, s2;
cin >> n;
vector<ll> a(n + 1);
for (ll i = 1; i <= n; i++)
{
cin >> a[i];
ma = max(a[i], ma); // 统计a[i]里的最大值
}
ans = 1; // ans 至少为 1
for (ll i = 1; i <= 2000;i++)
vis[i] = 0; // 重置vis数组
for (ll i = 1; i <= n; i++)
{
for (ll j = i + 1; j <= n; j++)
vis[a[i] + a[j]] = 1; // 可能的s值用vis数组去标记
}
for (ll s = 2; s <= ma * 2; s++) // 不用跑满2000，最多跑到2*ma即可
{
if (!vis[s]) // 没标记过的直接continue掉
continue;
for (ll i = 1; i <= n; i++)
dp[i][i] = (2 * a[i] == s) ? 1 : 0; // 只初始化对角线，其余状态通过直接赋值覆盖掉，这样就不会取旧值了
for (ll len = 2; len <= n; len++) // 枚举区间长度
{
for (ll l = 1; l + len - 1 <= n; l++) // 枚举区间左端点的起点
{
r = l + len - 1;
ll best = max(dp[l][r - 1], dp[l + 1][r]); // 当我们在判断dp[l][r]的时候，dp[l+1][r],dp[l][r-1],dp[l+1][r-1]都一定已经被考虑过了，所以直接取值即可，用best统计
if (a[l] + a[r] == s)
{
ll in = (r - l >= 2) ? dp[l + 1][r - 1] : 0; // 空区间视作是0
best = max(best, in + 2);
}
dp[l][r] = best; // 直接把best赋值给dp[l][r]
}
}
ans = max(ans, dp[1][n]);
if (ans == n) // ans如果已经到上限n了可以直接break了就
break;
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
LiangBaiKai();
int _ = 1;
cin >> _;
while (_--)
Aiden();
return 0;
}
/*
@@@@@@
@@@@@@@@@@
@@@@@@@@@@@@@
@@@@@@@@@@@@@@@
@@@@@@@@@@@
@@@@
@
@@@@@@@@@@ @@ @@@@@@@@@@@@
@@@@@ @ @@@@@
@@@ @ @@@
@@@ @@ @@@
@@ @@@
@@ @@
@@ @@
@@ @@
@ @@
@ @@@@@@@@ @@
@ @@@ @@@@@@@@@ @
@@ @@@@@@@ @@@@@@@@ @@@@@@ @
@ @@@@@@@@@@@@@@@@@@@@@@@@@@ @@
@ @@@@@@@@@@@ @@@@@@@@@@@ @
@@@@@@@@@@@@@ @@@@@@@@@@@@@@ @ @@@@@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @@@@@@ @@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@ @@@ @@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@
@@@@@@ @@@@@@@@@@ @@@@@@@@@@@@@@ @@
@@@@@ @@@@@@@ @@@@@@ @@ @@@@@@@@@@@ @@@
@@@@@ @@@@@@@@ @@@@ @@@@@@@ @@@@@@@@@@@ @@
@@@@@@ @@@@@@@ @@@@@ @@@@@@@ @@@@@@@@@@@@ @@@@@@@
@@@@@@@ @ @@@@@@ @@@@@@@ @@@@@@@@@@@@@@@@ @@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@ @ @@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ @ @ @@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ @@@@@ @ @@@@ @ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @@ @@ @@@ @@@@@ @@@@@@@@@@
@@@@@@@ @@@@@@@@@@@@@@ @@@@@@ @@@@@ @ @@@@@@@@
@@@@@@ @@@@@@@@@@@ @ @@@@@@@@
@@@@ @@@@@@@@ @@ @@@@@@@
@@ @@ @@@@@
@@@ @@
@@@ @@@
@@@@@@@@@@@@ @@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
*/
京公网安备 11010502036488号