大师
2024年12月25日大约 1 分钟
暴力枚举深搜
#include <bits/stdc++.h>
using namespace std;
int n;
int a[1005];
int ans;
bool flag[1005];
void dfs(int now)
{
if (now > n)
{
// 检查选择的数
bool up = true; // 是否等差
int d;
int last = -1; // 记录上一个选择的数
int cnt = 0; // 选了几个数
for (int i = 1; i <= n; i++)
if (flag[i])
{
cnt++;
if (cnt == 2)
d = a[i] - last;
else if (cnt > 2 && a[i] - last != d)
{
up = false;
break;
}
last = a[i];
}
if (cnt > 0 && up)
ans++;
return;
}
// 不选第 now 个数
flag[now] = false;
dfs(now + 1);
flag[now] = false;
// 选第 now 个数
flag[now] = true;
dfs(now + 1);
flag[now] = false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
ans = 0;
dfs(1);
cout << ans;
return 0;
}
优化
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int n;
int a[1005];
int book[1005][40000 + 5];
// 返回从 now 往后,公差为 d 的子序列数量
// 包括只有 1 项
int dfs(int now, int d)
{
if (book[now][d + 20000] != 0)
return book[now][d + 20000];
int res = 1;
for (int i = now + 1; i <= n; i++)
if (a[i] - a[now] == d)
{
// a[now],a[i],~~~~~
res += dfs(i, d);
res %= MOD;
}
return book[now][d + 20000] = res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
int ans = n; // 所有只有 1 项的
for (int d = -20000; d <= 20000; d++)
for (int i = 1; i <= n; i++)
{
ans += dfs(i, d) - 1; // 去掉只有 1 项的
ans %= MOD;
}
cout << ans;
return 0;
}
dp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 998244353;
const int BASE = 20000 + 5;
int n;
int a[1005];
//以 i 结尾,公差为 j 的最大长度
int dp[1005][20000 + BASE + 5];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
int ans = 0;
for (int i = 1; i <= n; i++)
{
ans++;
for (int j = i - 1; j >= 1; j--)
{
int d = a[i] - a[j] + BASE;
dp[i][d] = (dp[i][d] + dp[j][d] + 1) % MOD;
ans = (ans + dp[j][d] + 1) % MOD;
}
}
cout << ans << "\n";
return 0;
}