A.link
徐爷爷很强的用线段树切了，orz。正解大概是树形 dp 但是有 O(1) 的解法没想到吧...？
咕咕了，还不会。
B.link
赛时只会写 30pts 的暴力，感觉成飞舞了。
C.link
先写了一个二维 \(n^2\) 的暴力 dp。根据式子就可以优化掉一层循环，然后 \(O(n*a[i])\) 就有 60pts 的好成绩了。
然后就不会了。
赛后，很容易想到一个性质：温度差不会超过 \(O(\sqrt{C})\)。
据此能把复杂度降到 \(O(n\sqrt{C})\)。
但是这个飞舞自以为写了很对的东西调了很久一直挂到 40pts。还是很不理解。顺便附上码。
60pts:
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
const int inf=0x3f3f3f3f;
int n,m;
int a[N];
int f[N][N];
int maxn,ans=inf,t;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
maxn=max(maxn,a[i]);
}
memset(f,inf,sizeof f);
for(int i=1;i<=maxn;i++) f[1][i]=(a[1]-i)*(a[1]-i);
for(int i=2;i<=n;i++){
t=inf;
for(int j=1;j<=maxn;j++) if(j!=a[i]) t=min(t,f[i-1][j]);
for(int j=1;j<=maxn;j++)
f[i][j]=(a[i]-j)*(a[i]-j)+min(f[i-1][j],t+m);
}
for(int i=1;i<=maxn;i++) ans=min(ans,f[n][i]);
printf("%d",ans);
}
这是修改后的 40pts 的码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e4+10;
const int M=1010;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n,m;
int a[N];
ll f[N][M];
ll ans=inf,t;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
int k=sqrt(m);
memset(f,0x3f,sizeof f);
for(int i=-k;i<=k;i++) f[1][310+i]=i*i;
for(int i=2;i<=n;i++){
t=inf;
for(int j=-k;j<=k;j++) if(j+a[i-1]!=a[i]) t=min(t,f[i-1][j+310]);
for(int j=-k;j<=k;j++)
f[i][j+310]=j*j+min(f[i-1][a[i]-a[i-1]+j+310],t+m);
}
for(int i=310-k;i<=310+k;i++) ans=min(ans,f[n][i]);
printf("%lld",ans);
}
总结：杨神的模拟赛。感觉质量很高。