首页 > 其他分享 >1.11模拟赛 T1题解

1.11模拟赛 T1题解

时间:2024-01-11 16:25:36浏览次数:27  
标签:1.11 int 题解 top T1 最大值 sum define

简要题意

image
\(n\le 10^3 , \sum K_i\le3\times10^5\)

思路

首先容易想到一个暴力DP,\(f_{l,r,x}\) 表示区间中最大值为 \(x\) 的最大值

稍微想亿下可以发现如果这个位置选的不是区间最大值的话,答案一定不优
所以我们可以直接 \(f_{l,r}\) DP转移,但复杂度还是没变,我们把柿子列出来
\(f_{l,r}=max_{p\in[l,r]}(f_{l,p-1}+f_{p+1,r}+V_{p,k}*sum-C_{p,k})\)

发现这个函数是凸的,于是我们考虑斜率优化,然后改变枚举顺序,再然后就做完了

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1005
#define M 300005
int n,top,m;
int Q[N][N],cnt[N][N],sum[N][N],f[N][N];
struct A{
	int x,y;
}d[M],q[M];
vector<A> g[N];
bool cmp(A a,A b){
	if(a.x!=b.x) return a.x<b.x;
	return a.y<b.y;
}
int xiao(A a,A b,A c,A d){
	return (__int128)(b.y-a.y)*(d.x-c.x)<(__int128)(d.y-c.y)*(b.x-a.x);
}
void add(A p){
	if(p.x==q[top].x) return ;
	while(top>1&&xiao(q[top],p,q[top-1],q[top])) top--;
	q[++top]=p;
}
int cal(int k,int x,int y){
	return k*x-y;
}
signed main(){
	freopen("war.in","r",stdin);
	freopen("war.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			scanf("%lld",&Q[i][j]);
			cnt[i][j]=cnt[i-1][j]+Q[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++) sum[i][j]=sum[i][j-1]+cnt[j][j]-cnt[i-1][j];
	}
	for(int i=1;i<=n;i++){
		scanf("%lld",&m);
		for(int j=1;j<=m;j++) scanf("%lld%lld",&d[j].x,&d[j].y);
		sort(d+1,d+1+m,cmp);top=0;
		for(int j=1;j<=m;j++) add(d[j]);
		for(int j=1;j<=top;j++) g[i].push_back(q[j]);
	}
	memset(f,-127,sizeof(f));
	for(int i=0;i<=n;i++) f[i+1][i]=0;
	for(int l=n;l>=1;l--){
		for(int p=l;p<=n;p++){
			int i=0;
			for(int r=l;r<=n;r++){
				int he=sum[l][r]-sum[l][p-1]-sum[p+1][r];
				while(i<g[p].size()-1&&cal(he,g[p][i].x,g[p][i].y)<cal(he,g[p][i+1].x,g[p][i+1].y)) i++;
				f[l][r]=max(f[l][r],f[l][p-1]+f[p+1][r]+cal(he,g[p][i].x,g[p][i].y));
			}
		}
	}
	printf("%lld\n",f[1][n]);
	return 0;
}

标签:1.11,int,题解,top,T1,最大值,sum,define
From: https://www.cnblogs.com/hubingshan/p/17958812

相关文章

  • AT_joisc2018_b 题解
    AT_joisc2018_b题解传送门题意有一个以原点为中心的正方形,有\(n(n\le100)\)条不在正方形内部的线段,你需要画一些不在正方形内部的线段,使得这些线段可以把正方形围起来,要求最小化你画的线段的长度和。思路我们需要画出一条闭合折线,并且能够把正方形包围。考虑我们一定是......
  • 1.11模拟赛 T2题解
    简要题意每个点有一定概率向前面的点连边,求两点之间距离的期望思路推柿子code#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineN1000005intn,m,u,v;constintmod=1e9+7;inta[N],sum[N],c[N],dep[N],s[N],f[N],g[N],h[N];intksm(intx......
  • P4103 [HEOI2014] 大工程 题解
    题目链接:大工程先考虑只有一次查询,很显然我们可以暴力树上dp处理出答案。对于每个节点而言,有:容易看出类似点分治逐个遍历子树计算前面一堆子树对后面子树的贡献思想,我们可以很容易的知道:对于路径总和,显然多了一段新的贡献,这段贡献为当前关键点和前面点多的一段\(2\)号路......
  • 全志T113开发板Qt远程调试
    1引言通常情况下工程师在调试Qt程序时,需要频繁制作镜像烧录到核心板来测试Qt程序是否完善,这样的操作既费时又费力。这时我们可以通过QtCreator设备功能,定义设备后,在x86_64虚拟机上交叉编译qt程序,将程序远程部署到arm64的机子上,然后远程调试,大大提高开发效率。2. 调试环境本文基于H......
  • 全志T113开发板Qt远程调试
    1引言 通常情况下工程师在调试Qt程序时,需要频繁制作镜像烧录到核心板来测试Qt程序是否完善,这样的操作既费时又费力。这时我们可以通过QtCreator设备功能,定义设备后,在x86_64虚拟机上交叉编译qt程序,将程序远程部署到arm64的机子上,然后远程调试,大大提高开发效率。  2. 调试......
  • 《算法竞赛》题解---三分
    三分法模板三分法#include<bits/stdc++.h>#defineeps1e-8//或者constdoubleeps=1e-8;--主要是doubleusingnamespacestd;intn;doublea[15],l,r;doublecheck(doublex){ doubleans=0; for(inti=n;i>=0;i--) ans=ans*x+a[i];//秦九韶公式 returnans;}......
  • P4093 [HEOI2016/TJOI2016] 序列 题解
    题目链接:序列对于LIS问题,很显而易见的有dp方程为:\[dp_i=\max{dp_j}+1\(j<i,a_j\lea_i)\text{dp表示以某个位置结尾的最长LIS}\]本题考虑到对于转移的两位置,如果能从\(j\rightarrowi\),那么在以上条件成立的基础情况下,我们由于可以更改二者中的任意一个值(因为同一......
  • 2023 百度之星决赛题解
    T4传信游戏建反向边,从入度为\(0\)的结点开始搜T5喵喵卫士,全靠你了\(\star\)考虑暴力枚举每个点的深度,发现只要知道相邻两层的深度就能用组合数算方案数,自然想到按层DP,把上一层的点数记到状态里赛时做法按深度从小到大DP的话想要记录每个点是否被用过,以保证深度达到上......
  • P3203 弹飞绵羊 题解
    QuestionP3203[HNOI2010]弹飞绵羊一条直线上摆着\(n\)个弹簧,每个弹簧有一个弹力系数\(k_i\),当绵羊走到第\(i\)个弹簧时,会被弹到第\(i+k_i\)个弹簧,如果\(i+k_i>n\)则会被弹飞,有两个操作1x查询\(x\)处的绵羊经过几次会被弹飞2xy把\(x\)处的弹力系数改成......
  • P1307题解
    思路1.定义及输入原数/反转后的数intn,cnt=0;//反转后的数一定要归零!cin>>n;2.用while循环反转while(n!=0){//只要n还没有被分解完,就继续分解cnt=cnt*10+n%10;//cnt每次*10再加上分离出的数位(*10为了防0)n/=10;//n减一位}3.输出cout<<cnt;至此,这道题就做完......