斜率优化DP入门_HDU3507_Print Article
一次开火车遇到的知识盲区,只能从基础入门了,找了一个hdu的题学习了一发。
个人比较喜欢纸质笔记,字丑见谅。
#include <bits/stdc++.h> const long long mod = 1e9+7; const double ex = 1e-10; #define inf 0x3f3f3f3f #define iinf 0x3f3f3f3f3f3f3f3f using namespace std; long long dp[500011]; long long sum[500011]; int Q[500011]; double getk(int a,int b) // get the slope { if (dp[a]+sum[a]*sum[a] - dp[b]-sum[b]*sum[b] ==0 ) return 0; if (sum[a]==sum[b]) return 1e233; return (1.0*dp[a]+1.0*sum[a]*sum[a] - 1.0*dp[b]-1.0*sum[b]*sum[b])/(2.0*(sum[a]-sum[b])); } int main() { int N,M; while (cin >> N >> M) { memset(dp,iinf,sizeof(dp)); memset(sum,0,sizeof(sum)); dp[0] = 0; int a; for (int i = 1;i<=N; i++){ scanf("%d",&a); sum[i]+=sum[i-1]+a; } int head=2 , tail = 1; Q[1] = 0; for (int i = 1;i<=N;i++){ while (head>tail+1 && sum[i]>getk(Q[tail+1],Q[tail])) tail++; // Find the best shift && Drop some shift because of the increase of sum dp[i] = dp[Q[tail]] + M + ( sum[i] - sum[Q[tail]] ) * ( sum[i] - sum[Q[tail]] );//Shift while (head>tail+1 && getk(i,Q[head-1])<getk(Q[head-1],Q[head-2])) head--;//Insert the shift i && Maintain the increase of the slope Q[head++] = i;//Insert i } cout << dp[N] <<endl; } return 0; }