网站建设需求书模板,wordpress wiki模板,网站的管理维护,如何为网站添加谷歌分析工具题目链接 分析#xff1a; 目前为止我只能理解dp部分 我就喜欢这种单纯不做作的题目 一看名字就明白了这道题的本质 中二的题目描述 很显然#xff0c;我们的关键就是求出最小相似度 朴素算法n^4 如果我们现在有一个权值数组 显然#xff0c;每一个数只可能与最邻近ta的… 题目链接 分析 目前为止我只能理解dp部分 我就喜欢这种单纯不做作的题目 一看名字就明白了这道题的本质 中二的题目描述 很显然我们的关键就是求出最小相似度 朴素算法n^4 如果我们现在有一个权值数组 显然每一个数只可能与最邻近ta的数产生贡献 假设我们要求[i,j]之间的最小差距 那我们可以分成两部分[i,k],[k1,j] 枚举k取最小就可以了 但是这样的复杂度是n^3 然而我们全然不用枚举这个k f[i][j]abs(a[i]-a[j]) //i1j f[i][j]min{f[i1][j],f[i][j-1],abs(a[i]-a[j])} //j-i1 那还是n^2的我们考虑能不能再次优化去掉一维 空间i的转移只牵扯到i和i-1所以可以滚粗动数组 更进一步因为当前状态i需要用到i1的状态所以我们倒着推 每次让当前的覆盖上一次的上式中f[i][j]需要用到f[i1][j]的结果现在的话直接继承 这样我们就可以在空间上直接去掉一维 f[i]min(f[i],f[i-1]) 注意转换成一维后f[i]表示的是终点在i的区间 最终算法 实际上的基于dp的分类讨论 如果一个区间的长度是x那么最小差值一定不超过m/(x-1) 那么我们设一个常数ssqrt(n) 当x s时用算法一中的算法求解。 当xs时那么最小差不会超过 m/(s-1) 我们枚举差值|z-x|m/(s-1) ,然后找到权值z最近一次出现的位置然后计算答案 但是这样还是不够我们必须保证两个位置之间不存在再小的差值 所以我们还需要一个数组g[i]来记录差值i最近一次出现的位置 那么g[i]1一定是在差值i1或者更大的范围内所以用posx-g[i]-1)*(i1)来更新答案 详尽题解 这里写代码片
#includecstdio
#includecstring
#includeiostream
#includecmath
#define ll long longusing namespace std;const int N200002;
int n,m,k;
int pos[N],g[N];
ll f[N];
ll a[N],ans0;ll abs(ll x){if (x0) return x; else return -x;}int main()
{scanf(%d%d%d,n,m,k);for (int i1;in;i) scanf(%lld,a[i]);int sfloor(sqrt(n));memset(f,127,sizeof(f)); //INFfor (int in;i1;i--){for (int ji1;jmin(n,is-1);j) //只做块内的{f[j]min(f[j],f[j-1]);f[j]min(f[j],abs(a[j]-a[i]));if (j-i1k) ansmax(ans,(ll)(j-i)*f[j]);} }for (int i1;in;i){int tm/s;for (int j0;jt1;j){ll yya[i]j;ll ya[i]-j;if (j1) g[j]max(g[j-1],g[j]);if (y1) g[j]max(g[j],pos[y]);if (yym) g[j]max(g[j],pos[yy]);if (i-g[j]1max(s,k)) ansmax(ans,(ll)(i-g[j]-1)*(ll)(j1));}pos[a[i]]i;}printf(%lld\n,ans);return 0;
}转载于:https://www.cnblogs.com/wutongtong3117/p/7673197.html
