关于宏定义和函数
  • 板块学术版
  • 楼主alpharchmage
  • 当前回复3
  • 已保存回复3
  • 发布时间2025/1/13 10:28
  • 上次更新2025/1/13 15:46:11
查看原帖
关于宏定义和函数
411141
alpharchmage楼主2025/1/13 10:28

斜率优化板子 玩具装箱

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n = 0 , L = 0 , l = 1 , r = 0;
array<int , 500100> val , pre , dp , que;
//#define X(id) pre[id]
//#define Y(id) dp[id] + (pre[id] + L) * (pre[id] + L)
inline int X(int id)
{
	return pre[id];
}
inline int Y(int id)
{
	return dp[id] + (pre[id] + L) * (pre[id] + L);
}
inline long double slope(int a , int b)
{
	return (long double)((Y(b) - Y(a)) / (X(b) - X(a)));
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////  
	cin >> n >> L;
	++ L;
	//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////  
	for(int i = 1;i <= n;++ i)
	{
		cin >> val[i];
		pre[i] = pre[i - 1] + val[i] + 1;
	}
	//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////  
	que[++ r] = 0;
	for(int i = 1;i <= n;++ i)
	{
		while(l < r && slope(que[l] , que[l + 1]) <= 2 * pre[i]) ++ l;
		int nxt = que[l];
		dp[i] = dp[nxt] + (pre[i] - pre[nxt] - L) * (pre[i] - pre[nxt] - L);
		while(l < r && slope(que[r - 1] , que[r]) >= slope(que[r - 1] , i)) -- r;
		que[++ r] = i;
	}
	//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////  
	cout << dp[n] << endl;
	return 0; 
 } 

6~15行那里为什么用宏定义全错,用函数就对了呢?

2025/1/13 10:28
加载中...