题面
问题描述
WYF 从小就爱乱顶，但是顶是会造成位移的。他之前水平有限，每次只能顶出 $k$ 的位移，也就是从一个整点顶到另一个整点上。我们现在将之简化到数轴上，即从一个整点可以顶到与自己相隔在 $k$ 之内的数轴上的整点上。现在 WYF 的头变多了，于是他能顶到更远的地方，他能顶到任意整点上。现在他在玩一个游戏，这个游 戏里他只能向正方向顶，同时如果他从 $i$ 顶到 $j$，他将得到 $a_j \times (j - i)$ 的分数，其中 $a_j$ 是 $j$ 点上的分数，且要求 $j > i$, 他最后必须停在 $n$ 上。 现给出 $1～n$ 上的所有分数，原点没有分数。他现在在原点，没有分。WYF 想知道他最多能得多少分。
输入格式
第一行一个整数 $n$。 第二行有 $n$ 个整数，其中第 $i$ 个数表示 $a_j$。
$n \leq 100000, 0 \leq a_j \leq 50$
输出格式
一个整数，表示 WYF 最多能得到的分数。
题解
考场版
首先根据题面意思，可以直接得出以下式子：
\[dp_{j} = max_{i<j} dp_{i} + a_{j} \times (j-i)\]这样复杂度是$\Theta(n^2)的，只能得到60pts，因此考虑优化。
发现其实枚举了很多无意义的东西，因为计算 $dp_j$ 时不好确定最佳的 $i$（即$dp_i - a_j \times i$的最大值），但如果倒过来呢？（其实没什么差异，只是考场上就这样脑抽了下）
我们又可以得到以下式子：
\[dp_i = min_{i<j} dp_j + a_i \times (j-i)\]此时与 $j$ 相关的是 $dp_j + a_i \ times j$。再一看数据范围，$0 \leq a_j \leq 50$，范围这么小，可以对每个不同的 $a_j$ 缓存对应的 $dp$ 值和对应位置。
int n;
ll a[100010],b[100010],dp[51],dp2[51];
inline void solve(){
IO::read(n);
for(int i=1;i<=n;++i)IO::read(a[i]);
dp[a[n]]=0;
dp2[a[n]]=n;
for(int i=n-1;i>=0;--i){
for(int j=0;j<=50;++j){
b[i]=max(b[i],dp[j]+j*(dp2[j]-i));
}
if(b[i]>=dp[a[i]]+(dp2[a[i]]-i)*a[i]){
dp[a[i]]=b[i];
dp2[a[i]]=i;
}
}
IO::putln(b[0]);
}
考后版
考完后竟然听说，有巨佬用李超线段树写了这个T1，以为自己写的算简单的了。
直到现在看提交记录，发现还有更简单的方法。。。
$a_j \times (j-i)$ 本来的意义就是将 $a_j$ 重复 $j-i$ 遍，可以理解成是将 $a_j$ 填充到了 $(i,j]$ 这个区间内。
那么题目不就是要求 $[1,n]$ 和的最大值吗？只是加入了每个数只能往它本身的位置及以前填充的限制。
所以从后往前扫，每次加上到目前为止的最大值即可。
int n;
ll a[100010],maxx=0;
inline void solve(){
IO::read(n);
for(int i=1;i<=n;++i)IO::read(a[i]);
ll ans=0;
for(int i=n;i>=1;--i){
maxx=max(maxx,a[i]);
ans+=maxx;
}
IO::putln(ans);
}