前言

分数不算高，100 + 37 + 0，但为什么就排到靠前了？？

T1 – Snakes

原题地址

一句话题面：$n$ 个数分成 $k+1$ 组，要求每组最大值和每个值的差之和的总和最少。

挺水的一个 DP，转移有修改捕网大小和不修改两种，不修改用 ST 表求最大值记录一下最后一段的代价，修改直接转移。

$f[i][j]$ 表示当前第 $i$ 只蛇，已经修改过 $j$ 次的最小代价。

$$f\lbrack i\rbrack\lbrack j\rbrack=min\left\{\begin{array}{l}\begin{array}{l}f\lbrack i-1\rbrack\lbrack j-1\rbrack\;(j>0 时)\\f\lbrack k-1\rbrack\lbrack j-1\rbrack+max(s\lbrack k\rbrack,s\lbrack k+1\rbrack,……,s\lbrack i-1\rbrack,s\lbrack i\rbrack)\ast(i-k+1)-(sum\lbrack i\rbrack-sum\lbrack k-1\rbrack)\;(k=1\sim i-1)\end{array}\end{array}\right.$$

不过细节挺多，调了很久，具体看代码

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
int n,q,s[500],sum[500],F[1001][10],f[405][405];
void rmq(){
	for(int i=1;i<=n;i++){
		F[i][0]=s[i];
	}
	int t=log2(n);
	for(int j=1;j<=t;j++){
		for(int i=1;i<=n-(1<<j)+1;i++){
			F[i][j]=max(F[i][j-1],F[i+(1<<j-1)][j-1]);
		}
	}
}
int getmax(int L,int R){
	if(L>R) return -1;
	int t=log2(R-L+1);
	return max(F[L][t],F[R-(1<<t)+1][t]);
}
int ans=2147483647;
int main(){
    n=read();q=read();
    for (int i=1;i<=n;i++){
    	s[i]=read();
    	sum[i]=sum[i-1]+s[i];
	}
	rmq();
	f[1][0]=0;
	for (int i=2;i<=n;i++){
		for (int j=0;j<=q&j<=i-1;j++){
			f[i][j]=2147483647;
			for (int k=1;k<=i-1;k++){
				if (j==0&&k>1){
					break;
				}
				f[i][j]=min(f[k-1][j-1]+getmax(k,i)*(i-k+1)-(sum[i]-sum[k-1]),f[i][j]);
			}
			if (j>0){
				f[i][j]=min(f[i-1][j-1],f[i][j]);
			}
		}
	}
	for (int j=1;j<=q;j++){
		ans=min(ans,f[n][j]);
	}
	cout<<ans<<endl;
	return 0;
}

T2 – I Would Walk 500 Miles

原题地址

因为懒贴个 LG 题解上来

考的时候没想到，有大佬在考场上直接推出结论了 Orz

#include <bits/stdc++.h>
using namespace std;
int n,k;
int main () {
    cin>>n>>k;
    cout<<-12*(7*(k-1)+4*n)+2019201997;
}

T3 -Valleys

原题地址

直接贴题解吧

Image Source : https://blog.csdn.net/qq_39972971/article/details/89296244