【题目来源】
洛谷：P4933 大师 - 洛谷
【题目描述】
ljt12138 首先建了 \(n\) 个特斯拉电磁塔，这些电塔排成一排，从左到右依次标号为 \(1\) 到 \(n\)，第 \(i\) 个电塔的高度为 \(h[i]\)。
建筑大师需要从中选出一些电塔，然后这些电塔就会缩到地下去。这时候，如果留在地上的电塔的高度，从左向右构成了一个等差数列，那么这个选择方案就会被认为是美观的。
建筑大师需要求出，一共有多少种美观的选择方案，答案模 \(998244353\)。
注意，如果地上只留了一个或者两个电塔，那么这种方案也是美观的。地上没有电塔的方案被认为是不美观的。
同时也要注意，等差数列的公差也可以为负数。
【输入】
第一行一个正整数 \(n\)。
第二行 \(n\) 个非负整数，第 \(i\) 个整数是第 \(i\) 个电塔的高度 \(h[i]\)。
【输出】
输出一个整数，表示美观的方案数模 \(998244353\) 的值。
【输入样例】
8
13 14 6 20 27 34 34 41
【输出样例】
50
【解题思路】
【算法标签】
《洛谷 P4933 大师》 #动态规划,dp# #枚举# #洛谷月赛# #O2优化#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 1005; // 定义最大数组长度
const int MOD = 998244353; // 定义模数int n; // 数组长度
int ans; // 美观方案总数
int a[N]; // 存储序列元素
int f[N][N]; // dp数组，f[i][j]表示以a[i]和a[j]结尾的美观子序列数int main()
{// 输入序列长度cin >> n;// 输入序列元素for (int i = 1; i <= n; i++){cin >> a[i];}// 初始化答案：每个单独元素都构成一个美观方案ans = (ans + n) % MOD;// 动态规划计算美观子序列数for (int i = 1; i < n; i++){for (int j = i + 1; j <= n; j++){f[i][j] = 1; // 基础情况：a[i]和a[j]本身构成一个长度为2的子序列// 计算当前两数差值int x = a[j] - a[i];// 查找前面能与当前差值形成等差数列的元素for (int k = 1; k < i; k++){if (x == a[i] - a[k]) // 找到满足等差条件的元素{f[i][j] = (f[i][j] + f[k][i]) % MOD; // 累加方案数}}// 累加到总答案中ans = (ans + f[i][j]) % MOD;}}// 输出结果cout << ans;return 0;
}
【运行结果】
8
13 14 6 20 27 34 34 41
50