虽然AC了但还是不懂
查看原帖
虽然AC了但还是不懂
707424
monkeys_King楼主2024/1/16 14:40

这是ACAC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 50004;
long long n , l;
long long c[N]; 
long long sum[N] , dp[N] , q[N] , head , tail;
long long a(long long k)
{
	return sum[k] + k;
}
long long b(long long k)
{
	return sum[k] + k + l + 1;
}
double qx(long long k)
{
	return b(k);
}
double qy(long long k)
{
	return dp[k] + (b(k) * b(k));
}
double slope(long long x1 , long long x2)
{
	return (qy(x1) - qy(x2)) / (qx(x1) - qx(x2));
}
int main()
{
	cin >> n >> l;
	for(long long i = 1 ; i <= n ; i++)
	{
		cin >> c[i];
		sum[i] = sum[i - 1] + c[i];
	}
	head = tail = 1;
	for(long long i = 1 ; i <= n ; i++)
	{
		while(head < tail && slope(q[head] , q[head + 1]) < 2 * a(i)) ++head;
		dp[i] = dp[q[head]] + (a(i) - b(q[head])) * (a(i) - b(q[head]));
		while(head < tail && slope(q[tail - 1] , q[tail]) > slope(i , q[tail - 1])) --tail;
		q[++tail] = i;
	}
	//for(int i = 1 ; i <= n ; i++) cout << dp[i] << " ";
	cout << dp[n];
	return 0;
}

这是WAWA代码

#include <bits/stdc++.h>
using namespace std;
const int N = 50004;
long long n , l;
long long c[N]; 
long long sum[N] , dp[N] , q[N] , head , tail;
long long a[N] , b[N];
double qx(long long k)
{
	return b[k];
}
double qy(long long k)
{
	return dp[k] + b[k] * b[k];
}
double slope(long long x1 , long long x2)
{
	return (qy(x1) - qy(x2)) / (qx(x1) - qx(x2));
}
int main()
{
	cin >> n >> l;
	sum[0] = 0;
	for(long long i = 1 ; i <= n ; i++)
	{
		cin >> c[i];
		sum[i] = sum[i - 1] + c[i];
	}
	for(long long i = 1 ; i <= n ; i++)
	{
		a[i] = sum[i] + i;
		b[i] = sum[i] + i + l + 1;
	}
	head = tail = 1;
	for(long long i = 1 ; i <= n ; i++)
	{
		while(head < tail && slope(q[head] , q[head + 1]) < 2 * a[i]) ++head;
		dp[i] = dp[q[head]] + (a[i] - b[q[head]]) * (a[i] - b[q[head]]);
		while(head < tail && slope(q[tail - 1] , q[tail]) > slope(i , q[tail - 1])) --tail;
		q[++tail] = i;
	}
	//for(int i = 1 ; i <= n ; i++) cout << dp[i] << " ";
	cout << dp[n] - 160;
	return 0;
}
我只是把a和b拿到主函数里求,为什么不对。a,b不是定值吗?
2024/1/16 14:40
加载中...