二进制分组优化多重背包
index = 0;
for (int i = 1; i <= m; i++) {int c = 1, p, h, k;cin >> p >> h >> k;while (k > c) {k -= c;list[++index].w = c * p;list[index].v = c * h;c *= 2;}list[++index].w = p * k;list[index].v = h * k;
}
单调队列优化多重背包
#include <array>
#include <deque>
#include <iostream>constexpr int MAXV = 4e4 + 10;
constexpr int MAXN = 1e2 + 10;using namespace std;int n, W, last = 0, now = 1;
array<int, MAXN> v, w, k;
array<array<int, MAXV>, 2> f;
deque<int> q;int main() {ios::sync_with_stdio(false);cin >> n >> W;for (int i = 1; i <= n; i++) {cin >> v[i] >> w[i] >> k[i];}for (int i = 1; i <= n; i++) {for (int y = 0; y < w[i]; y++) {// 清空队列deque<int>().swap(q);for (int x = 0; x * w[i] + y <= W; x++) {// 弹出不在范围的元素while (!q.empty() && q.front() < x - k[i]) {q.pop_front();}// 保证队列单调while (!q.empty() && f[last][q.back() * w[i] + y] - q.back() * v[i] <f[last][x * w[i] + y] - x * v[i]) {q.pop_back();}q.push_back(x);f[now][x * w[i] + y] =f[last][q.front() * w[i] + y] - q.front() * v[i] + x * v[i];}}swap(last, now);}cout << f[last][W] << endl;return 0;
}
数位dp
#include<bits/stdc++.h>
using namespace std;typedef unsigned long long ull;ull f[20][10],power[20];
void init() {power[0]=1;for(int i=1;i<=19;i++) power[i]=power[i-1]*10;for(int i=0;i<=9;i++) f[1][i]=1;for(int i=2;i<=19;i++)for(int j=0;j<=9;j++)for(int k=0;k<=9;k++)if(abs(j-k)>=2)f[i][j]+=f[i-1][k];return ;
}
ull solve(ull x) {int w=0,y,pre;ull ans=0;while(power[w]<=x) w++;for(int i=1;i<w;i++)for(int j=1;j<=9;j++)ans+=f[i][j];y=x/power[w-1];for(int j=1;j<y;j++) ans+=f[w][j];pre=y,x%=power[w-1];for(int i=w-1;i>=1;i--) {y=x/power[i-1];for(int j=0;j<y;j++)if(abs(j-pre)>=2)ans+=f[i][j];if(abs(pre-y)<2) break;pre=y,x%=power[i-1];}return ans;
}int main() {ull a,b;cin>>a>>b;init();cout<<solve(b+1)-solve(a)<<endl;return 0;
}
斜率优化（玩具装箱）
#include<bits/stdc++.h>
using namespace std;#define db double
#define int long long
const int maxn = 1e6+10;int n,L,v[maxn];
int f[maxn],sum[maxn];
int q[maxn],hd,tl;inline int read(){int x = 0,f = 0;char c = getchar();while(!isdigit(c))f|=(c=='-'),c = getchar();while(isdigit(c))x = x*10+c-'0',c = getchar();if(f)x = -x;return x;
}db a(int x){return sum[x]+x;
}db b(int x){return sum[x]+x+L+1;
}db X(int x){return a(x);
}db Y(int x){return f[x]+b(x)*b(x);
}db slope(int x,int y){return (Y(y) - Y(x))/(X(y) - X(x));
}signed main(){#ifndef ONLINE_JUDGEfreopen("in.in","r",stdin);freopen("out.out","w",stdout);#endifn = read(),L = read();for(int i=1;i<=n;i++){int x = read();sum[i] = sum[i-1]+x;}hd = tl = 1;for(int i=1;i<=n;i++){while(hd<tl&&slope(q[hd],q[hd+1])<2*a(i))hd++;f[i] = f[q[hd]]+(a(i) - b(q[hd]))*(a(i) - b(q[hd]));while(hd<tl&&slope(q[tl-1],q[tl])>slope(q[tl-1],i))tl--;q[++tl] = i;}printf("%lld\n",f[n]);return 0;
}
二分队列四边形不等式（诗人小G）
#include <bits/stdc++.h>
#define ll long doubleusing namespace std;const int maxn = 1e6 + 10;
int T;
int p, n, pr[maxn], nxt[maxn], h, t;
ll a[maxn], s[maxn], le, f[maxn], q[maxn], r[maxn];
char c[maxn][40];ll qpow(ll a, int b) {ll res = 1;while (b) {if (b & 1)res = res * a;a = a * a;b >>= 1;}return res;
}ll calc(int i, int j) {return (f[j] + qpow(abs(s[i] - s[j] - 1 - le), p));
}int bound(int x, int y) {int l = x, r = n + 1;while (l < r) {int mid = (l + r) >> 1;if (calc(mid, x) >= calc(mid, y))r = mid;elsel = mid + 1;}return l;
}int main() {
#ifndef ONLINE_JUDGEfreopen("in.in", "r", stdin);freopen("out.out", "w", stdout);
#endifscanf("%d", &T);while (T--) {scanf("%d%Lf%d", &n, &le, &p);memset(f, 0x3f, sizeof(f));memset(pr, 0, sizeof(pr));memset(nxt, 0, sizeof(nxt));for (int i = 1; i <= n; ++i) {scanf("%s", c[i]);a[i] = (ll)strlen(c[i]) + 1;s[i] = s[i - 1] + a[i];}q[h = t = 1] = 0, r[h = t = 1] = n;f[0] = 0;for (int i = 1; i <= n; ++i) {while (h < t && r[h] < i)++h;f[i] = calc(i, q[h]), pr[i] = q[h];while (h < t && r[t - 1] >= bound(q[t], i))--t;r[t] = bound(q[t], i) - 1, q[++t] = i;}if (f[n] > 1e18) {puts("Too hard to arrange");}else {printf("%0.Lf\n", f[n]);int x = n;while (pr[x]) {nxt[pr[x]] = x;x = pr[x];}nxt[0] = x;x = 0;while (nxt[x]) {for (int i = x + 1; i < nxt[x]; ++i) {printf("%s ", c[i]);}printf("%s\n", c[nxt[x]]);x = nxt[x];}}puts("--------------------");}return 0;
}
分治决策单调性（魔法商店）
#include <bits/stdc++.h>
using namespace std;#define int long long
const int maxn = 2e6 + 10;namespace IO {
void openfile() {
#ifndef ONLINE_JUDGEfreopen("in.in", "r", stdin);freopen("out.out", "w", stdout);
#endif
}inline int read() {int x = 0, f = 0;char c = getchar();while (!isdigit(c))f |= c == '-', c = getchar();while (isdigit(c))x = x * 10 + c - '0', c = getchar();if (f)x = -x;return x;
}
} // namespace IO
using namespace IO;int n, m, k;
int sum[10][maxn];
int c[maxn], v[maxn], sta[10][maxn], top[maxn];
int f[10][maxn], now[maxn], num;void dp(int pos, int l, int r, int x, int y) {if (l > r)return;int mid = (l + r) >> 1, p = mid;for (int i = max(x, mid - top[pos]); i <= min(mid, y); i++)if (f[pos - 1][now[i]] + sum[pos][mid - i] >= f[pos - 1][now[p]] + sum[pos][mid - p])p = i;//这个位置一定要是>=因为p如果是mid可能会大于等于y，这样右区间就没有决策区间了f[pos][now[mid]] = f[pos - 1][now[p]] + sum[pos][mid - p];dp(pos, l, mid - 1, x, p), dp(pos, mid + 1, r, p, y);
}bool cmp(int x, int y) {return x > y;
}signed main() {openfile();n = read(), m = read(), k = read();for (int i = 1; i <= n; i++) {c[i] = read(), v[i] = read();sta[c[i]][++top[c[i]]] = v[i];}for (int i = 1; i <= 7; i++)sort(sta[i] + 1, sta[i] + 1 + top[i], cmp);for (int i = 1; i <= 7; i++)for (int j = 1; j <= top[i]; j++)sum[i][j] = sum[i][j - 1] + sta[i][j];memset(f, -0x7f, sizeof(f));f[0][0] = 0;for (int i = 1; i <= 7; i++) {for (int j = 0; j < min(m + 1, i); j++) {for (int k = j; k <= m; k += i)now[++num] = k;dp(i, 1, num, 1, num);for (int k = 1; k <= num; k++)now[k] = 0;num = 0;}}// for (int i = 1; i <= 7; i++) {// for (int j = 0; j <= m; j++)// cout << f[i][j] << ' ';// cout << endl;// }int ans = 0;for (int i = 1; i <= m; i++) {ans = max(ans, f[7][i]);printf("%lld\n", ans);}cerr << 1.0 * clock() / CLOCKS_PER_SEC << '\n';return 0;
}
slope trick（P4331 [BalticOI 2004] Sequence 数字序列）
#include <bits/stdc++.h>
using namespace std;#define int long long
#define pii pair<int, int>
#define mp make_pair
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;namespace IO {
void openfile() {
#ifndef ONLINE_JUDGEfreopen("in.in", "r", stdin);freopen("out.out", "w", stdout);
#endif
}int mul(int x, int y) {return 1ll * x * y % mod;
}int add(int x, int y) {x += y;if (x >= mod)x -= mod;return x;
}int sub(int x, int y) {return add(x, mod - y);
}inline int read() {int x = 0, f = 0;char c = getchar();while (!isdigit(c))f |= c == '-', c = getchar();while (isdigit(c))x = x * 10 + c - '0', c = getchar();if (f)x = -x;return x;
}
} // namespace IO
using namespace IO;int n, a[maxn];
int top, ans;
int b[maxn], ls[maxn], rs[maxn], tot, dis[maxn];struct node {int rt, l, r, siz, val;
} sta[maxn];int merge(int x, int y) {if (!x || !y)return x + y;if (a[x] < a[y])swap(x, y);rs[x] = merge(rs[x], y);if (dis[ls[x]] < dis[rs[x]])swap(ls[x], rs[x]);dis[x] = dis[rs[x]] + 1;return x;
}int del(int x) {return merge(ls[x], rs[x]);
}signed main() {openfile();dis[0] = -1;n = read();for (int i = 1; i <= n; i++)a[i] = read() - i;for (int i = 1; i <= n; i++) {sta[++top] = {i, i, i, 1, a[i]};while (top != 1 && sta[top - 1].val > sta[top].val) {top--;sta[top].rt = merge(sta[top].rt, sta[top + 1].rt);sta[top].siz += sta[top + 1].siz;sta[top].r = sta[top + 1].r;while (sta[top].siz > (sta[top].r - sta[top].l + 2) / 2)sta[top].siz--, sta[top].rt = del(sta[top].rt);sta[top].val = a[sta[top].rt];}}int cnt = 1;for (int i = 1; i <= n; i++) {if (sta[cnt].r < i)++cnt;ans += abs(sta[cnt].val - a[i]);}printf("%lld\n", ans);cnt = 1;for (int i = 1; i <= n; i++) {if (sta[cnt].r < i)++cnt;printf("%lld ", sta[cnt].val + i);}puts("");cerr << 1.0 * clock() / CLOCKS_PER_SEC << '\n';return 0;
}
