这是AC代码
#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;
}
这是WA代码
#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不是定值吗?