kuangbin 斜率优化题单代码

1. HDU-3507 Print Article

$f_i = \min_{0 \le j < i} \{ f_j + (s_i - s_j)^2 + M \}$

// https://vjudge.net/problem/HDU-3507
#include 
using namespace std;
/*
fi = min{ fj + (si-sj)^2 + m }

k fj + (si-sj)^2 + m
fk + sk^2 - 2*si*sk > fj + sj^2 - 2*si*sj
sj^2 - sk^2 + fj - fk < si*2*(sj-sk)
((sj^2+fj)-(sk^2+fj)) / (2*sj - 2*sk) < si

xi = 2*si
yi = si^2 + fi
*/

#define MAXN 500005

int n, m;

long long c[MAXN];
long long s[MAXN];
long long x[MAXN], y[MAXN];
long long f[MAXN];

int q[MAXN], ql, qr;

bool solve()
{
    if (scanf("%d%d", &n, &m)!=2) return false;
    for (int i=1; i<=n; i++) {
        scanf("%lld", &c[i]);
        s[i] = s[i-1]+c[i];
    }

    ql=1;
    qr=0;
    q[++qr] = 0;
    for (int i=1; i<=n; i++) {

        while (ql<qr && (y[q[ql+1]] - y[q[ql]]) <= s[i]*(x[q[ql+1]] - x[q[ql]]))    // 注意要加上等于号
            ql++;
        f[i] = f[q[ql]] + (s[i] - s[q[ql]])*(s[i] - s[q[ql]]) + m;
        x[i] = 2*s[i];
        y[i] = s[i]*s[i] + f[i];

        while (ql<qr && ((y[i] - y[q[qr]])*(x[q[qr]]-x[q[qr-1]]) <= (y[q[qr]]-y[q[qr-1]])*(x[i]-x[q[qr]])))
            qr--;
        q[++qr] = i;
    }

    printf("%lld\n", f[n]);
    return true;
}


int main()
{
    while (solve());
    return 0;
}


/*

5 5
5 9 5 7 5

*/
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

2. HDU-2829 Lawrence

$f_{m,i} = \min_{m < j < i} \{ f_j + \frac{(s_i - s_j)^2 - (t_i - t_j)}{2} \}$

#include 

/*
s[k] = Sum[ai, {i, 1, k}]
t[k] = Sum[ai^2, {i, 1, k}]

fi = min{ fj + ((si-sj)^2 - (ti-tj)) / 2 }

k

#define MAXN 1000

int n, m;
long long s[MAXN];
long long t[MAXN];
long long dp[MAXN][MAXN];   // ans = dp[m+1][n]

int q[MAXN], ql, qr;

long long get_up(int k, int j, long long *f)
{
    return (2*f[j] + s[j]*s[j] + t[j]) - (2*f[k] + s[k]*s[k] + t[k]);
}

long long get_down(int k, int j)
{
    return ((s[j]-s[k])<<1);
}


bool solve()
{
    int tmp;
    scanf("%d%d", &n, &m);
    if ((n|m) == 0) return false;
    for (int i=1; i<=n; i++) {
        scanf("%d", &tmp);
        s[i] = s[i-1] + tmp;
        t[i] = t[i-1] + tmp*tmp;
    }

    for (int i=1; i<=n; i++) {
        dp[1][i] = (s[i]*s[i]-t[i])/2;
    }

    for (int mm=2, maxmm=m+1; mm<=maxmm; mm++) {
        ql = 1;
        qr = 0;
        q[++qr] = mm-1;     // 注意前面至少有 mm-1 个，所以一开始入队列的是 mm-1

        for (int i=mm; i<=n; i++) {
            while (ql<qr && get_up(q[ql], q[ql+1], dp[mm-1]) <= get_down(q[ql], q[ql+1])*s[i])
                ql++;
            dp[mm][i] = dp[mm-1][q[ql]] + ((s[i]-s[q[ql]])*(s[i]-s[q[ql]]) - (t[i]-t[q[ql]]))/2;

            while (ql<qr && get_up(q[qr-1], q[qr], dp[mm-1])*get_down(q[qr], i) >= get_up(q[qr], i, dp[mm-1])*get_down(q[qr-1], q[qr]))
                qr--;
            q[++qr] = i;
        }
    }

    printf("%lld\n", dp[m+1][n]);

    return true;
}


int main()
{
    while (solve());
    return 0;
}


/*

4 1
4 5 1 2

4 2
4 5 1 2

0 0

17 2


20 5
23 95 77 90 77 69 24 84 73 9 37 11 28 33 42 39 64 18 91 6 
49824

7 3
65 63 99 3 31 16 84 
4732

10 6
63 97 45 93 42 82 94 8 40 9 
4196

10 8
37 71 3 16 74 91 5 40 40 49 
48

5 3
5 4 3 2 1


*/
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

4. HDU-1300 Pearls

$f_i = \min_{0 \le j < i} \{ f_j + (s_i - s_j + 10)*p_i \}$

#include 
/*
p[i] < p[i+1]

si = a1+a2+...+ai
fi = min{ fj + (si-sj+10)*mxp[j+1..i] }
fi = min{ fj + (si-sj+10)*p[i]}

k

#define MAXN 200

int n;
long long a[MAXN];
long long p[MAXN];
long long s[MAXN];
long long f[MAXN];

long long q[MAXN], ql, qr;

long long get_up(int k, int j)
{
    return f[j]-f[k];
}

long long get_down(int k, int j)
{
    return s[j]-s[k];
}

void solve()
{
    scanf("%d", &n);
    for (int i=1; i<=n; i++) {
        scanf("%lld%lld", &a[i], &p[i]);
        s[i] = s[i-1]+a[i];
    }

    ql=1;
    qr=0;
    q[++qr] = 0;
    for (int i=1; i<=n; i++) {
        while (ql<qr && get_up(q[ql], q[ql+1]) <= p[i] * get_down(q[ql], q[ql+1]))
            ql++;
        f[i] = f[q[ql]] + (s[i]-s[q[ql]]+10)*p[i];

        while (ql<qr && get_up(q[qr-1], q[qr])*get_down(q[qr], i) >= get_up(q[qr], i)*get_down(q[qr-1], q[qr]))
            qr--;
        q[++qr] = i;
    }

    printf("%lld\n", f[n]);
}


int main()
{
    int ttt;
    scanf("%d", &ttt);
    while (ttt--) {
        solve();
    }
    return 0;
}

/*

2
100 1
100 2
330

3
1 10
1 11
100 12
1344

5
6 3
4 3
4 5
9 9
8 9
339
*/
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

5. HDU-2993 MAX Average Problem

这题卡读入优化有点骚
这题是纯斜率的，和前面几题有点不同，不过也没有差太多。可以说是另一类板子题吧。
https://blog.csdn.net/qq_36294918/article/details/103641411
$f_i = \max_{0 \le j \le i-k} \{ \frac{s_i - s_j}{i - j} \}$

#include 

/*
fi = max{ (si-sj)/(i-j) , 0<=j<=i-k }

k (si-sk)/(i-k)
(si-sj)*(i-k) > (si-sk)*(i-j)

*/

#define MAXN 100005

int n, m;
int a[MAXN];
int s[MAXN];
int f[MAXN];
int q[MAXN], ql, qr;
double ans;


inline char __getchar()
{
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline bool qread(int &x)
{
	char ch=__getchar();
	if(ch==EOF)return false;
	x=0;
	while(!(ch>='0'&&ch<='9'))ch=__getchar();
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=__getchar();
    return x;
}

double max(const double &x, const double &y) {return x<y?y:x;}
double get_k(int x, int y) {return 1.0*(s[y]-s[x])/(y-x);}

int solve()
{
    if (!qread(n) || !qread(m)) return false;
    for (int i=1; i<=n; i++) qread(a[i]), s[i] = s[i-1]+a[i];

    ql=1;
    qr=0;
    ans=0;

    for (int i=m, ii=0; i<=n; i++, ii++) {
        while (ql<qr && get_k(q[qr-1], q[qr])>=get_k(q[qr], ii))
            qr--;
        q[++qr] = ii;

        while (ql<qr && get_k(q[ql], i)<=get_k(q[ql+1], i))
            ql++;
        
        ans = max(ans, get_k(q[ql], i));
    }

    printf("%.2f\n", ans);

    return true;
}


int main()
{
    while (solve());
    return 0;
}

/*
10 6
6 4 2 10 3 8 5 9 4 1
6.50
*/
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

相关阅读:
7、内网安全-横向移动&PTH哈希&PTT票据&PTK密匙&Kerberos&密码喷射
Web3.0简介
使用kubasz快速搭建Kubernetes集群
Android Camera App启动流程解析
Mac上使用Charles抓包
代码随想录算法训练营第day14|二叉树理论基础、二叉树递归遍历、二叉树迭代遍历
Linux多核运行机制（SMP）
如何导出带有材质的GLB模型？
从零开始教你dubbo自定义负载均衡策略
2-9.基金管理人公司治理和风险管理

原文地址：https://blog.csdn.net/jackypigpig/article/details/125797683

kuangbin 斜率优化题单 代码

1. HDU-3507 Print Article

2. HDU-2829 Lawrence

4. HDU-1300 Pearls

5. HDU-2993 MAX Average Problem

kuangbin 斜率优化题单代码