【dp优化】股票交易 玩具装箱 Watching Fireworks is Fun

#include <stdio.h> // 做法:设f[i]为时刻i的最小等待时间
#include <string.h> // f[i]=min{f[j]+i(cnt[i]-cnt[j])-(sum[i]-sum[j])}
#include <algorithm> // cnt为前i个的个数,sum为j<=i的j的和
const int N = 4000105; // 法1: 优化:去掉冗余状态和无意义转移: 1.j在[i-2m,i-m],2.如果cnt[i]=cnt[i-m]则直接f[i]=f[i-m]
typedef long long LL; // 法2: 斜率优化
int cnt[N], n, m, t, q[N];
LL sum[N], f[N];
int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1, x; i <= n; i ++)
		scanf("%d", &x), cnt[x] ++, sum[x] += x, t = std::max(t, x);
	for(int i = 1; i < t + m; i ++) cnt[i] += cnt[i-1], sum[i] += sum[i-1];
	int hh = 0, tt = -1;
	for(int i = 0; i < t + m; i ++) {
#		define val(I) LL(f[I] + sum[I])
		if(i >= m) {
			while(hh < tt && (val(q[tt]) - val(q[tt-1])) * LL(cnt[i-m] - cnt[q[tt]]) >= LL(cnt[q[tt]] - cnt[q[tt-1]]) * (val(i-m) - val(q[tt]))) tt --;
			q[++ tt] = i-m;
		}
		while(hh < tt && (val(q[hh+1]) - val(q[hh])) <= i * LL(cnt[q[hh+1]] - cnt[q[hh]])) hh ++;
		f[i] = cnt[i] * i - sum[i];
		if(hh <= tt) f[i] = std::min(f[i], f[q[hh]] + LL(cnt[i] - cnt[q[hh]]) * i - (sum[i] - sum[q[hh]]));
	} LL res = 9e18;
	for(int i = t; i < t + m; i ++) res = std::min(res, f[i]);
	printf("%lld\n", res);
	return 0;
}

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <utility>
#include <queue>

using namespace std;

typedef long long LL;

const int N = 100005, M = 100005, P = 105;

int n, m, p;
LL d[N], t[N], a[N], s[N];
LL f[P][M];
int q[M];

int main() {
	scanf("%d%d%d", &n, &m, &p);
	for(int i = 2; i <= n; i ++) {
		scanf("%lld", d + i);
		d[i] += d[i - 1];
	}
	for(int i = 1, h; i <= m; i ++) {
		scanf("%d%lld", &h, t + i);
		a[i] = t[i] - d[h];
	}
	sort(a + 1, a + m + 1);
	for(int i = 1; i <= m; i ++) s[i] = s[i - 1] + a[i];
	// 初始化: f[i][0]=0, 其余为 inf
	for(int i = 0; i <= p; i ++)
		for(int j = 1; j <= m; j ++) f[i][j] = 0x3f3f3f3f3f3f3f3fLL;
	for(int j = 1; j <= p; j ++) {
		int hh = 0, tt = 0;
		q[0] = 0; // 下凸
		for(int i = 1; i <= m; i ++) {
#define y(k, j) (f[j - 1][k] + s[k]) // 方便实现的宏
			while(hh < tt && (y(q[hh + 1], j) - y(q[hh], j)) <= a[i] * (q[hh + 1] - q[hh])) hh ++;
#define k q[hh]
			f[j][i] = f[j - 1][k] - a[i] * k + s[k] + a[i] * i - s[i];
			while(hh < tt && (y(q[tt], j) - y(q[tt - 1], j)) * (i - q[tt]) >= (y(i, j) - y(q[tt], j)) * (q[tt] - q[tt - 1])) tt --;
			q[++ tt] = i;
		}
	}
	printf("%lld\n", f[p][m]);
	return 0;
}

#include <stdio.h>
#include <string.h>
const int N = 150005, M = 305;
typedef long long LL;
int n, m, d, a[N], b[N], t[N];
LL f[2][N]; int q[N];
int main() {
	scanf("%d%d%d", &n, &m, &d);
	for(int i = 1; i <= m; i ++) scanf("%d%d%d", a + i, b + i, t + i);
	for(int i = 1; i <= m; i ++) {
		memset(f[i&1], -0x3f, sizeof(f[i&1]));
		for(int j = 1, hh = 0, tt = -1, k = 1; j <= n; j ++) {
			for(; k <= n && k <= j + d * LL(t[i] - t[i - 1]); k ++) {
				while(hh <= tt && f[(i-1)&1][q[tt]] <= f[(i-1)&1][k]) tt --;
				q[++ tt] = k;
			}
			while(hh <= tt && q[hh] < j - d * LL(t[i] - t[i - 1])) hh ++;
			f[i&1][j] = f[(i-1)&1][q[hh]] - (a[i] > j ? a[i] - j : j - a[i]) + b[i];
		}
	} LL res = -0x3f3f3f3f3f3f3f3fLL;
	for(int i = 1; i <= n; i ++) if(res < f[m&1][i]) res = f[m&1][i];
	printf("%I64d\n", res);
	return 0;
}

// f[i][j]:第i天j支股票
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int N = 2005;
int n, m, w, f[N][N], ap, bp, as, bs, q[N];
int main() {
	scanf("%d%d%d", &n, &m, &w);
	memset(*f, -0x3f, sizeof(*f));
	for(int i = 1; i <= n; i ++) {
		scanf("%d%d%d%d", &ap, &bp, &as, &bs);
		memset(f[i], -0x3f, sizeof(f[i]));
		for(int j = 0; j <= as; j ++) f[i][j] = -ap * j;
		for(int j = 0; j <= m; j ++) f[i][j] = std::max(f[i][j], f[i-1][j]);
		if(i > w) {
			int hh = 0, tt = -1;
			for(int j = 0; j <= m; j ++) {
				while(hh <= tt && q[hh] < j - as) hh ++;
				while(hh <= tt && f[i-w-1][q[tt]] + q[tt] * ap <= f[i-w-1][j] + j * ap) tt --;
				q[++ tt] = j, f[i][j] = std::max(f[i][j], f[i-w-1][q[hh]] - (j - q[hh]) * ap);
			}
			hh = 0, tt = -1;
			for(int j = m; j >= 0; j --) {
				while(hh <= tt && q[hh] > j + bs) hh ++;
				while(hh <= tt && f[i-w-1][q[tt]] + q[tt] * bp <= f[i-w-1][j] + j * bp) tt --;
				q[++ tt] = j, f[i][j] = std::max(f[i][j], f[i-w-1][q[hh]] + (q[hh] - j) * bp);
			}
		}
	}
	int res = -0x3f3f3f3f;
	for(int i = 0; i <= m; i ++) res = std::max(res, f[n][i]);
	printf("%d\n", res);
	return 0;
}

#include <iostream> // f[i]表示将前i个玩具装箱的最小花费
#include <stdio.h> // f[i] = max { f[j] + (...)**2 }
const int N = 5e4 + 5; // 化简: 将i的和常数放在一项, j的放在另一项
typedef long long LL; // f[j]+(..)**2 = 2*某*(..) + f[i] - 常数
typedef __int128_t LLL;
int n, q[N]; LL s[N], l, f[N]; // s为前缀和+i (方便处理)
int main() {
	scanf("%d%lld", &n, &l), l ++; // l++: 方便处理
	for(int i = 1, c; i <= n; i ++) scanf("%d", &c), s[i] = s[i-1] + c + 1;
	int hh = 0, tt = 0;
	for(int i = 1; i <= n; i ++) {
#		define v(I) (f[I] + (LLL)(s[I] + l) * (s[I] + l))
		while(hh < tt && (v(q[hh+1]) - v(q[hh])) <= LLL(2) * s[i] * (s[q[hh+1]] - s[q[hh]])) hh ++;
		f[i] = f[q[hh]] + (s[i] - l - s[q[hh]]) * (s[i] - l - s[q[hh]]);
		while(hh < tt && (v(q[tt]) - v(q[tt-1])) * LLL(s[i] - s[q[tt]]) >= (v(i) - v(q[tt])) * LLL(s[q[tt]] - s[q[tt-1]])) tt --;
		q[++ tt] = i;
	}
	printf("%lld\n", f[n]);
	return 0;
}