斜率优化dp代码实现c++
时间: 2023-10-04 22:05:54 浏览: 42
以下是斜率优化DP的C++代码实现,供您参考:
```c++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
ll dp[maxn], c[maxn], sum[maxn], h[maxn], q[maxn], n, m;
int head, tail;
int main()
{
scanf("%lld %lld", &n, &m);
for(int i = 1; i <= n; i++) scanf("%lld", &h[i]);
for(int i = 1; i <= n; i++) sum[i] = sum[i-1]+h[i];
head = tail = 1;
for(int i = 1; i <= n; i++)
{
while(head < tail && q[head+1] <= i) head++;
dp[i] = dp[q[head]] + (sum[i]-sum[q[head]]) - (i-q[head])*h[q[head]];
c[i] = h[i];
while(head < tail && (c[q[tail]]-c[q[tail-1]])*(i-q[tail]) >= (c[i]-c[q[tail]])*(q[tail]-q[tail-1])) tail--;
q[++tail] = i;
while(head < tail && (c[q[head+1]]-c[q[head]]) <= i*(h[q[head+1]]-h[q[head]])) head++;
}
printf("%lld\n", dp[n]*m);
return 0;
}
```
这段代码实现的是一道题目,使用了斜率优化DP。