关于slope函数的类型的疑问求解答1关
  • 板块AT_dp_z Frog 3
  • 楼主ivyjiao
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/8/28 21:00
  • 上次更新2024/8/28 23:12:28
查看原帖
关于slope函数的类型的疑问求解答1关
578029
ivyjiao楼主2024/8/28 21:00

rt,这是我的代码:

//dp[i] = min(dp[j]+(h[i]-h[j])^2+C)
//dp[i] = dp[j]+(h[i]-h[j])^2+C
//dp[i] = dp[j]+h[i]^2-2*h[i]*h[j]+h[j]^2+C
//dp[i] = dp[j]+h[i]^2-2*h[i]*h[j]+h[j]^2+C
//dp[j]+h[j]^2 = 2*h[i] * h[j] + dp[i]-h[i]^2-C
//     y       =   k    *  x   +       b
//启动!
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,C,a[200001],dp[200001],q[200001];
int X(int j){
	return a[j];
}
int Y(int j){
	return dp[j]+pow(a[j],2);
}
double query(int i,int j){
	return 1.0*(Y(j)-Y(i))/(X(j)-X(i));
}
signed main(){
	cin>>n>>C;
	for(int i=1;i<=n;i++) cin>>a[i];
    int h=1,t=1;
    q[1]=1;
	for(int i=2;i<=n;i++){
		while(h<t&&query(q[h],q[h+1])<=2*a[i]) h++;
		dp[i]=dp[q[h]]+pow(a[i]-a[q[h]],2)+C;
		while(h<t&&query(q[t-1],i)<=query(q[t-1],q[t])) t--;
		q[++t]=i;
	}
	cout<<dp[n];
}
  1. 为什么我在 slope(query)函数中仅仅是把函数类型从 int 改为 double 就 AC 了?
  2. 为什么我在另一道板子 P3195 [HNOI2008] 玩具装箱 中没出现这种情况?

原代码:

int query(int i,int j){
	return (Y(j)-Y(i))/(X(j)-X(i));
}
2024/8/28 21:00
加载中...