首页 > 其他分享 >TypeDB Forces 2023 C. Remove the Bracket

TypeDB Forces 2023 C. Remove the Bracket

时间:2023-01-31 00:11:10浏览次数:61  
标签:TypeDB ch cdot 200100 mi Remove int Bracket mx

链接:https://codeforces.com/contest/1787/problem/C
题意:给定数组a数n和s,再由\(x_i+y_i=a_i\)且\((x_i-s) \cdot (y_i-s) \geq 0\)一个式子令其值最小 $ F = a_1 \cdot x_2+y_2 \cdot x_3+y_3 \cdot x_4 + \ldots + y_{n - 2} \cdot x_{n-1}+y_{n-1} \cdot a_n $,
其中n,s<=2e5,a[i]<=2e5.
观察发现 \(F = a_1 \cdot (x_2+y_2) \cdot (x_3+y_3) \cdot x_4 + \ldots + y_{n - 2} \cdot (x_{n-1}+y_{n-1}) \cdot a_n\),s对每个xi,yi的作用是将其限制在一个值域中,容易求得上下界。发现对于每个a[i]=x[i]+y[i],设左数l右数r,若l==r,如何拆分无所谓;l<r,x[i]=max,y[i]=min;l>r,x[i]=min,y[i]=max;故可知每个x[i]只有两种取值,故dp即可。
代码:

#define int long long
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
	if (t<0) { putchar('-'); write(-t); return; }
	if (t>9) write(t/10);
	putchar('0'+t%10);
}
int a[200100],mx[200100],mi[200100],f[200100][3];
void solve(){
	int n,s;cin>>n>>s;
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=2;i<=n-1;i++){
		if(s>a[i]){
			mi[i]=0,mx[i]=a[i];
			continue;
		}
		int minx=a[i]-s,maxx=s;
		int u=min(minx,maxx),v=max(minx,maxx);
		mi[i]=u,mx[i]=v;
	}
	mi[1]=mx[1]=a[1],mi[n]=mx[n]=a[n];
	int ans=0;
	for(int i=1;i<=n;i++){
		f[i][1]=min(f[i-1][0]+mx[i-1]*mx[i],f[i-1][1]+mi[i-1]*mx[i]);
		f[i][0]=min(f[i-1][0]+mx[i-1]*mi[i],f[i-1][1]+mi[i-1]*mi[i]);
	}
	ans=min(f[n][0],f[n][1]);
	cout<<ans<<endl;
}
signed main(){
	int T;read(T);
	while(T--) solve();
}

标签:TypeDB,ch,cdot,200100,mi,Remove,int,Bracket,mx
From: https://www.cnblogs.com/wjhqwq/p/17077603.html

相关文章

  • TypeDB Forces 2023 E. The Harmonization of XOR
    链接:https://codeforces.com/contest/1787/problem/E题意:给定n,有一个数组a,满足其所有元素均为1~n,给定k,问能否将数组拆为k个,其每一组的xor为x。我们发现任意三个xor为k的......
  • TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!)(持续更新)
    Preface猜结论场,很久没打比赛了然后赛前和ztc吹牛说每次隔一段时间来打CF就会有强运加持结果好家伙BCE全部秒出结论(而且我比赛时都证不来),而且写的A~E都是一发入魂凭借这......
  • TypeDB Forces 2023 (Div. 1 + Div. 2)
    题目链接A核心思路直接把其中一个数置为1就好了。//Problem:A.ExponentialEquation//Contest:Codeforces-TypeDBForces2023(Div.1+Div.2,Rated,Priz......
  • TypeDB Forces 2023 (Div. 1 + Div. 2) 题解
    更新中……A~D略。E.TheHarmonizationofXOR题目链接题意简述\(t\)组testcase,每组给定\(n,k,x\)三个数。求将\(1\simn\)划分成\(k\)个子序列(可以不连......
  • [CF380C] Sereja and Brackets 题解
    [CF380C]SerejaandBrackets题解给定一个括号串\(s\)与\(m\)次询问。l,r回答字符串\(t=s_ls_{l+1}\dotss_r\)​的所有子序列中最长的合法括号串的长度。......
  • notepad++ 替换空行 Remove empty lines and spaces in Notepad++?
    RemoveemptylinesandspacesinNotepad++?回答1Togetridofleadingspace(s)andallemptylines(eveniftheemptylinecontainsspacesortabs)Goto S......
  • JQuery的remove方法的使用
    jquery的remove方法是将元素移除掉,并且返回被移除的元素,还可以使用,下面一个例子使用该功能实现下图的功能:<!DOCTYPEhtml><htmlxmlns="http://www.w3.org/1999/xhtml"><hea......
  • VK Cup 2022 F. Bracket Insertion
    有一个初始为空的括号序列,依次执行\(n(n\le500)\)次操作,每次有\(p\)的概率选取(),\(1-p\)的概率选取)(,随机插入首部、尾部、中间的空隙(也就是从\(2i-1\)个位置中......
  • 关于Session方法之Abandon、Clear和RemoveAll
     学习Asp.net有n年了,也一直在使用Session这个宝贝,这个宝贝的确好用,可是一直也没有时间好好总结一下他的几个方法,知道近日有学生问起,才好好总结了一下,下面就是他们的区别和......
  • list.remove()时出问题,集合的remove方法注意事项2
    不要在foreach循环里进行元素的remove/add操作。remove元素请使用Iterator方式,如果并发操作,需要对Iterator对象加锁。另可参考:​list.remove()时出问题,集合的re......