本文涉及知识点C动态规划大师题目背景建筑大师最近在跟着数学大师 ljt12138 学数学今天他学了等差数列ljt12138 决定给他留一道练习题。题目描述ljt12138 首先建了n nn个特斯拉电磁塔这些电塔排成一排从左到右依次标号为1 11到n nn第i ii个电塔的高度为h [ i ] h[i]h[i]。建筑大师需要从中选出一些电塔然后这些电塔就会缩到地下去。这时候如果留在地上的电塔的高度从左向右构成了一个等差数列那么这个选择方案就会被认为是美观的。建筑大师需要求出一共有多少种美观的选择方案答案模998244353 998244353998244353。注意如果地上只留了一个或者两个电塔那么这种方案也是美观的。地上没有电塔的方案被认为是不美观的。同时也要注意等差数列的公差也可以为负数。输入格式第一行一个正整数n nn。第二行n nn个非负整数第i ii个整数是第i ii个电塔的高度h [ i ] h[i]h[i]。输出格式输出一个整数表示美观的方案数模998244353 998244353998244353的值。样例 #1样例输入 #18 13 14 6 20 27 34 34 41样例输出 #150样例 #2样例输入 #2100 90 1004 171 99 1835 108 81 117 141 126 135 144 81 153 193 81 962 162 1493 171 1780 864 297 180 532 1781 189 1059 198 333 1593 824 207 1877 216 270 225 1131 336 1875 362 234 81 288 1550 243 463 1755 252 406 261 270 279 288 1393 261 1263 297 135 333 872 234 881 180 198 81 225 306 180 90 315 81 81 198 252 81 297 1336 1140 1238 81 198 297 661 81 1372 469 1132 81 126 324 333 342 81 351 481 279 1770 1225 549样例输出 #211153提示设v vv为最高的电塔高度。对于前30 % 30\%30%的数据$n \le 20 $。对于前60 % 60\%60%的数据n ≤ 100 n \le 100n≤100v ≤ 2 × 10 3 v \le 2 \times 10^3v≤2×103。对于另外20 % 20\%20%的数据所有电塔的高度构成一个等差数列。对于100 % 100\%100%的数据n ≤ 10 3 n \le 10^3n≤103v ≤ 2 × 10 4 v \leq2 \times 10^4v≤2×104。动态规划动态规划的状态表示dp[i][s] 表示以h[i]结束s为公差的长度至少2的等差数列的数量。空间复杂度O(nn)动态规划的填表顺序i从0到大枚举数列的最后一个数j从小到大枚举数量的倒数第二个数动态规划的转移返程s h[i]-h[j]dp[i][s] 1 dp[j][s]注意如果dp[j][s]不存在则不加。避免空间溢出。单个状态时间复杂度O(1)总时间复杂度O(nn)注意可能存在h[j1]h[j2]故处理完dp[i]后再统一更新ans。动态规划的初始值无动态规划的返回值∑ \sum∑dp h.size()代码核心代码#includeiostream#includesstream#includevector#includemap#includeunordered_map#includeset#includeunordered_set#includestring#includealgorithm#includefunctional#includequeue#includestack#includeiomanip#includenumeric#includemath.h#includeclimits#includeassert.h#includecstring#includelist#includebitsetusingnamespacestd;templateclassT1,classT2std::istreamoperator(std::istreamin,pairT1,T2pr){inpr.firstpr.second;returnin;}templateclassT1,classT2,classT3std::istreamoperator(std::istreamin,tupleT1,T2,T3t){inget0(t)get1(t)get2(t);returnin;}templateclassT1,classT2,classT3,classT4std::istreamoperator(std::istreamin,tupleT1,T2,T3,T4t){inget0(t)get1(t)get2(t)get3(t);returnin;}templateclassTintvectorTRead(){intn;scanf(%d,n);vectorTret(n);for(inti0;in;i){cinret[i];}returnret;}templateclassTintvectorTRead(intn){vectorTret(n);for(inti0;in;i){cinret[i];}returnret;}templateintMOD1000000007classC1097Int{public:C1097Int(longlongllData0):m_iData(llData%MOD){}C1097Intoperator(constC1097Into)const{returnC1097Int(((longlong)m_iDatao.m_iData)%MOD);}C1097Intoperator(constC1097Into){m_iData((longlong)m_iDatao.m_iData)%MOD;return*this;}C1097Intoperator-(constC1097Into){m_iData(m_iDataMOD-o.m_iData)%MOD;return*this;}C1097Intoperator-(constC1097Into){returnC1097Int((m_iDataMOD-o.m_iData)%MOD);}C1097Intoperator*(constC1097Into)const{return((longlong)m_iData*o.m_iData)%MOD;}C1097Intoperator*(constC1097Into){m_iData((longlong)m_iData*o.m_iData)%MOD;return*this;}C1097Intoperator/(constC1097Into)const{return*this*o.PowNegative1();}C1097Intoperator/(constC1097Into){*this/o.PowNegative1();return*this;}booloperator(constC1097Into)const{returnm_iDatao.m_iData;}booloperator(constC1097Into)const{returnm_iDatao.m_iData;}C1097Intpow(longlongn)const{C1097Int iRet1,iCur*this;while(n){if(n1){iRet*iCur;}iCur*iCur;n1;}returniRet;}C1097IntPowNegative1()const{returnpow(MOD-2);}intToInt()const{return(m_iDataMOD)%MOD;}private:intm_iData0;;};classSolution{public:typedefC1097Int998244353BI;intAns(constvectorinth){constintNh.size();vectorunordered_mapint,BIdp(N);BI ansN;for(inti0;iN;i){for(intj0;ji;j){constintsh[i]-h[j];dp[i][s]1;if(dp[j].count(s)){dp[i][s]dp[j][s];}}for(constauto[tmp,c]:dp[i]){ansc;}}returnans.ToInt();}};intmain(){#ifdef_DEBUGfreopen(a.in,r,stdin);#endif// DEBUGintn;cinn;autohReadint(n);autoresSolution().Ans(h);coutresendl;#ifdef_DEBUG/*printf(a0%d, a0);*///Out(h, h);#endif// DEBUGreturn0;}