前言
分数不算高,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
T2链接给错了…
修了