T1
考场用时：\(1\) h
期望得分：\(70\) pts
实际得分：\(20\) pts
有一个地方的 \(m\) 写成了 \(n\)，直接 T 飞。
对于 \(70\) 分的做法，考虑设 \(dp_{i,j}\) 表示分了 \(i\) 段，现在到 \(j\) 的最小代价，枚举 \(i\) 转移，复杂度 \(O(n^2 m)\)。
发现其实段数是没必要枚举的，直接压掉一维，复杂度 \(O(nm)\)，可以得 \(100\) pts。
int dp[20001],st[20001][21][2],lg[MAX];
inline int w(int l,int r){
int len=lg[r-l+1];
int mn=min(st[l][len][0],st[r-(1ll<<len)+1][len][0]);
int mx=max(st[l][len][1],st[r-(1ll<<len)+1][len][1]);
return mx-mn;
}
signed main(){
int n=read(),m=read(),K=read();
for(int i=1;i<=n;i++) dp[i]=1e18;
for(int i=1;i<=n;i++) st[i][0][0]=st[i][0][1]=read();
lg[0]=-1;
for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
for(int i=1;i<=20;i++)
for(int j=1;j+(1ll<<i)-1<=n;j++){
st[j][i][0]=min(st[j][i-1][0],st[j+(1ll<<(i-1))][i-1][0]);
st[j][i][1]=max(st[j][i-1][1],st[j+(1ll<<(i-1))][i-1][1]);
}
dp[0]=0;
for(int j=1;j<=n;j++){
for(int k=max(0ll,j-m);k<j;k++)
dp[j]=min(dp[j],dp[k]+w(k+1,j)*(j-k)+K);
}
cout<<dp[n];
return 0;
}
T2
考场用时:\(30\) min
期望得分：\(30\) pts
实际得分：\(0\) pts
爆搜写假了，考虑贪心，对于若干个连续的 \(1\)，如果只有 \(1\) 个，显然直接加上是最优的，对于答案的贡献是 \(1\)，如果有 \(\ge 2\) 个 \(1\)，假设有 \(x\) 个 \(1\)，此时可以花费 \(1\) 的代价构造出 \(1\) 后面跟着 \(x\) 个 \(0\)，然后再减 \(1\)，此时代价是 \(2\)，优于一个一个加。
具体实现可以从头到尾扫一遍字符串，记录当前连续 \(1\) 的个数，考虑反过来，按照以上原则，把 \(1\) 全部消掉。
char s[MAX];
signed main(){
int n=read();
scanf("%s",s+1);
int js=0,ans=0;
for(int i=1;i<=n;i++){
if(s[i]=='1') js++;
else{
if(js==1) ans++,js=0;
else if(js>1) ans++,js=1;
}
}
ans+=min(js,2ll);
cout<<ans;
return 0;
}