2019.9.15 校内模拟赛

前言

分数不算高,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

评论

  1. Eqvpkbz
    Windows Chrome
    1年前
    2019-9-21 20:22:40

    T2链接给错了…

    • solstice23 博主
      Windows Chrome
      1年前
      2019-9-21 21:56:17

      修了

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: Telegram @AmashiroNatsukiEars_NoWord Sticker
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
AmashiroNatsukiEars
小恐龙
花!
上一篇
下一篇