把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

HDU 3507 Print Article
题目大意：将一串数（5e5）分为多个部分，每个部分的价值为该部分数的和的平方+常数M，求最小能分出的价值。

解：

明摆着卡复杂度要求优化dp的题目，而且根据题意来看多半是优先队列，输入数据很多，记得用scanf。
列出式子之后发现主要的优化部分在于dp[i]（表示遍历到第i个物品时的最小价值）选择从哪个数转移得到，假设有k和j两个选择，通过构造fx可以得出f(k)-f(j)与其他kj相关函数的关系，在这题中以斜率的形式出现，也就是f(k)-f(j)/q(k)-q(j)<=C（与i有关，但其实无所谓），斜率有关的状态可以形成一条曲线，既然是比较斜率，那么唯一重要的就是凹凸性和常数的方向，可以注意到在这题中方向并不是固定的，因为取决于i，但无论方向在哪，都是要么斜率最大的点要么斜率最小的点是最优选择，所以中间的点可以直接消去，只留下最大和最小的，对于每个i判断一下最大和最小哪个才是最优解。
如果用单调队列来维护，单调队列最里面的值不能碰，（因为会需要同时保留一个最大值和一个最小值），也就是说该队列一定是至少有两个元素在里面的。
斜率dp在抽象的dp中也显得更加抽象，因为你甚至无法写出像样的方程，同时对于单调队列的理解也非常重要，可以从这道入门题来深入了解一下。
一般来讲为了效率和准确性会用移项把除法换成乘法，但这道题直接用double干过去了……

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#define ll long long
#define maxn 500005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(ll i=0;i<n;i++)a[i]=m;
#define endl '\n'using namespace std;
double a[maxn], dp[maxn], qzh[maxn];
int qr[maxn];
inline double xl(int j, int i) {
    if (qzh[i] == qzh[j])return 0;
    return (dp[i] + qzh[i] * qzh[i] - dp[j] - qzh[j] * qzh[j]) / (qzh[i] - qzh[j]);
}
int main() {
    cfast;
    int n;
    double m;
    while (scanf("%d%lf",&n,&m)!=EOF) {
        inc(i, 1, n + 1) {
            scanf("%lf",&a[i]);
            qzh[i] = qzh[i - 1] + a[i];
        }
        int head = 0, tail = 1;
        qr[0] = 0;
        inc(i, 1, n + 1) {
        //    cout << "xxxxxx " << xl(qr[head], qr[head + 1]) << endl;            while (head < tail && xl(qr[head], qr[head + 1]) <= 2 * qzh[i]) {
            //    cout << xl(qr[head], qr[head + 1]) << endl;                head++;
            }
            dp[i] = dp[qr[head]] + m + (qzh[i] - qzh[qr[head]]) * (qzh[i] - qzh[qr[head]]);
            while (head < tail && xl(qr[tail],i)<=xl(qr[tail-1],qr[tail])) {
            //    cout << xl(qr[tail], i) << " " << xl(qr[tail - 1], qr[tail]) << endl;                tail--;
            }tail++;
            qr[tail] = i;
        //    cout << head << " " << tail << endl;        }
        printf("%.0lf\n", dp[n]);
    }
}