笔记汇总
前言：
状态一般是可持续的。
状态机就是看当前状态受之前哪些状态的影响。
环形与后效性处理
P1
有两种状态，睡着、未睡着，注意入睡可以看作这两个状态间的边。
求最大值更新最小，第一维可以滚掉。
主要难点是初态设计：
初态是第一小时睡觉和不睡觉的情况，由于我们维护的是小时的结尾，所以不设第$0$小时。
因为 $j=0$ 和睡一小时矛盾，但与没有睡不矛盾，所以要提出来判断。
本题初始化 $-0x3f$ 是为了将 $j=0, st=1$ 的情况无解化。
环的开头和结尾都是处于睡觉状态（计划要有连续性）
/*
dp[i,j,0/1]在第i个小时，已经休息了j个小时，0表示这个小时没在休息，1表示这个小时正在休息。
属性: max
将环拆开, 计算链的贡献和首尾影响下的贡献
线性DP（状态机思想） + 环形结构
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 4e3 + 1;
int T, n, B;
int a[N];
int f[2][N][2];
int main()
{
int ans = 0;
scanf("%d%d", &n, &B);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
memset(f, -0x3f, sizeof f);
f[1][0][0] = f[1][1][1] = 0;
for (int i = 2; i <= n; i ++ )
{
f[i&1][0][0] = f[i-1&1][0][0];
for (int j = 1; j <= B; j ++ )
{
f[i&1][j][0] = max(f[i-1&1][j][1], f[i-1&1][j][0]);
f[i&1][j][1] = max(f[i-1&1][j-1][0], f[i-1&1][j-1][1] + a[i]);
}
}
ans = max(f[n&1][B][1], f[n&1][B][0]);
memset(f, -0x3f, sizeof f);
f[1][1][1] = a[1];
for (int i = 2; i <= n; i ++ )
{
f[i&1][0][0] = f[i-1&1][0][0];
for (int j = 1; j <= B; j ++ )
{
f[i&1][j][0] = max(f[i-1&1][j][1], f[i-1&1][j][0]);
f[i&1][j][1] = max(f[i-1&1][j-1][0], f[i-1&1][j-1][1] + a[i]);
}
}
ans = max(ans, f[n&1][B][1]);
printf("%d\n", ans);
}
注意，本题有三种终态（初态不同答案也不同）。
P2
本题变量有两个下标，数据 $10^6$，线性做法可过，所以不难想到单调队列优化。
想办法确认窗口大小，由于 $0 <= i-j <= 2/n$，破环成链，不难想到窗口大小是 $2/n$，
我们找到窗口内最大的 $A_j - j$。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
int n, a[N], q[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
scanf("%d", &a[i]), a[i + n] = a[i];
int hh = 0, tt = -1;
int len = n / 2;
int res = 0;
for (int i = 1; i <= n * 2; i ++ )
{
while (hh <= tt && q[hh] < i - len) hh ++;
res = max(res, a[i] + a[q[hh]] + i - q[hh]);
/*至少要有两座仓库，计算时不能让某座仓库的值乘以2
所以先算再往里插*/
while (hh <= tt && a[q[tt]] - q[tt] <= a[i] - i) tt --;
q[ ++ tt] = i;
}
printf("%d", res);
}
总结
将环形问题变为线性问题，用人类智慧处理环形特殊性。
方法一：
执行两次$DP$，第一次，在某一位置把环断开成链；第二次，计算断开位置强制连续时的贡献。
方法二：
断环成链复制一倍。
状压DP
挑战 $20min$ 写完，达成的题目链接放下面。
P1
二维平面的覆盖独立模型。
我们只保留涉及到的阶段的状态。
如何转移是合法的，那就计算最大值，我们规定枚举顺序从上往下，
由于状压$DP$储存了前几层的状态，我们可以就此得出之后层的 合法状态。
这个合法不仅对于当前阶段的前面几个转移成立，也对前面阶段的后面几个转移成立。
所以不需要考虑 $i+1, i+2$ 层，没有后效性。
P2
与上面的题不同，本题覆盖范围是不固定的。
我们需要先确定一种覆盖范围，其它的可以直接填，本题只有两种覆盖范围，所以此时贡献为 $1$。
我们发现对于填完横着的长方形之后，有解仅当剩下的空格长是偶数（不然填不了），
与之前不同的，我们储存的是第 $i$ 层的状态，不过$i-1$与$i$是相同的，所以其实也可以看成是 $i-1$ 层的状态（都要合法）。
我们之所以选择枚举链接两层的覆盖方式是为了便于转移。
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 12, M = 1 << N;
int n, m;
LL f[N][M];
vector<int> state[M];
bool st[M];
int main()
{
while (scanf("%d %d", &n, &m), n || m)
{
if (n & 1 && m & 1) // 无解 不可能填满奇数个格子
{
puts("0");
continue;
}
for (int i = 0; i < 1 << n; i ++ ) // 合法方案
{
int cnt = 0;
bool is_vaild = true;
for (int j = 0; j < n; j ++ )
{
if (i >> j & 1) // 1 是被覆盖，0 是未覆盖
{
if (cnt & 1) // 不能为奇数
{
is_vaild = false;
break;
}
}
else cnt ++;
}
if (cnt & 1) is_vaild = false;
st[i] = is_vaild;
}
for (int i = 0; i < 1 << n; i ++ ) // 合法转移
{
state[i].clear();
for (int j = 0; j < 1 << n; j ++ )
if ((i & j) == 0 && st[i | j])
{
state[i].push_back(j);
}
}
memset(f, 0, sizeof f);
f[0][0] = 1;
for (int i = 1; i <= m; i ++ ) // DP
for (int j = 0; j < 1 << n; j ++ )
{
for (int k = 0; k < state[j].size(); k ++ ) // i-1层
{
f[i][j] += f[i-1][state[j][k]];
}
}
printf("%lld\n", f[m][0]);
}
return 0;
}
C1
本题很像最小生成树，但边权费用计算有所不同，
我们将打通的宝藏屋的深度和状态作为阶段，可以用状态压缩$DP$解决。
#include <bits/stdc++.h>
using namespace std;
const int N = 15, M = 1 << 15, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int ne[M];
int f[M][N];
int get_cost(int cur, int pre)
{
if ((ne[pre] & cur) != cur) return -1;
int remain = pre ^ cur;
int cost = 0;
for (int i = 0; i < n; i ++ )
{
if (remain >> i & 1)
{
int t = INF;
for (int j = 0; j < n; j ++ )
if (pre >> j & 1)
t = min(t, g[j][i]);
cost += t;
}
}
return cost;
}
int main()
{
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);
for (int i = 0; i <= n; i ++ ) g[i][i] = 0;
for (int i = 1; i <= m; i ++ )
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
u --, v --;
g[u][v] = g[v][u] = min(g[u][v], w);
}
for (int st = 1; st < 1 << n; st ++ ) // 处理合法转移
for (int i = 0; i < n; i ++ )
if (st >> i & 1)
{
for (int j = 0; j < n; j ++ )
if (g[i][j] != INF)
{
ne[st] |= 1 << j;
}
}
memset(f, 0x3f, sizeof f);
for (int i = 0; i < n; i ++ ) f[1 << i][0] = 0; // 起点
for (int i = 1, cost; i < 1 << n; i ++ )
for (int j = (i-1)&i; j; j = (j-1)&i)
if (~(cost = get_cost(i, j)))
{
for (int k = 1; k < n; k ++ )
{
f[i][k] = min(f[i][k], f[j][k-1] + cost * k);
}
}
int res = INF;
for (int k = 0; k < n; k ++ )
res = min(res, f[(1 << n) - 1][k]); // 目标状态找最优解
printf("%d", res);
}
枚举子集的方法：
for(int j=(i-1)&i;j!=0;j=(j-1)&i);
计算距离这一块和 $Prim$ 有所不同：
这里算的是将生成树$pre$拓展为$cur$的最小花费。
省略掉了标记数组（状态压缩位代替）
$Prim$ 的思想是，最小生成树的边都是可选用的最小边权。
我们用反证法，可知如果有不是的就会存在更小的生成树，得证。
倍增DP
倍增$DP$具有子问题任意划分和多次询问的特点。
如果一个问题可以划分成一些更小的子问题，这些子问题之间可以通过某种运算得到原来问题的答案
这时，我们可以靠计算二的整次幂的子问题，组合得出答案。
这就是倍增$DP$，一种优化状态转移的$DP$。
C1
容易知道我们可以预处理小A小B从每个城市出发可到达的城市。
在处理之后，我们发现它们是互相独立的，可以组合（有任意划分性）
用类似LCA的方式O(nlogn)计算从城市i出发走2^k天到达哪个城市。
实际情况需要AB轮换, 我们还需要分别知道A,B两人行驶的总距离
用 Da, Db 存储
C2
字符串首尾相接，如果 $a$ 组可以生成，那么 $a$ 的正数倍线性组合组都可以生成，
如果想要整个最短等于让前一半最短再让后一半最短，有任意划分性。
$DP$ 问题一般是先做很多题，然后再去观察能不能用之前的方法套，然后将代码分成不同的功能块，就可以写出来了。
最好是多花时间想，剩下的时间写。
#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 30;
char s1[110], s2[110];
int n1, n2, f[N][M], n, m, L;
int main()
{
while (scanf("%s%d%s%d", s2, &n2, s1, &n1) == 4)
{
memset(f, 0, sizeof f);
n = strlen(s1), m = strlen(s2), L = log2(n * n1 / m);
// 从0~|s1|-1的下标i开始匹配s2所需最小字符数
for (int i = 0; i < n; i ++ ) // 从i开始看走多远可以走到j的每一个字母
for (int j = 0; f[i][0] <= n * m && j < m; f[i][0] ++ )
if(s2[j] == s1[(i + f[i][0]) % n]) j ++;
if (f[0][0] > n * m) { puts("0"); continue;} // 没有出现过，无解
for (int j = 1; j <= L; j ++ )
for (int i = 0; i < n; i ++ )
f[i][j] = f[i][j-1] + f[(i + f[i][j-1]) % n][j-1];
int p = 0, ans = 0;
for (int i = L; i >= 0; i -- ) // 这里是找要多少个才能拼，肯定是越靠前越好。
if (p + f[p%n][i] <= n * n1)
{
p += f[p%n][i];
ans += 1 << i; // 可以凑出多少个s2
}
printf("%d\n", ans / n2);
}
}
这一道题目简单概括就是求一个最大的$m$，使得字符串$s2$被复制$m*n2$之后是字符串$s1\*n1$的子序列。
更进一步进行简化：可以认为求一个最大的$t$，使得$s2$复制$t$次后是$s1$复制$n1$次的子序列。
$m=⌊tn2⌋$.
这是因为满足单调性：当复制$t$次是子序列，那么当小于$t$次，显然也是子序列。
当复制$t+1$次已经不是子序列，那么大于$t+1$时，同样不再是子序列。（因为有多余的在$s1*n1$无法找到）
在这里，首先认为$s1*INF$是无限多的。由于具有周期性，可以使用$0—size-1$的位置表示。
$f[i][j]$.指从第$i$个位置开始，得到$2^j$个重复的$s2$的子序列所需要的最短的长度。
数据结构优化DP
P1
贪心：
将所有区间按照左端点从小到大进行排序
从前往后枚举每个区间，在所有能覆盖$start$的区间中，选择右端点的最大区间，然后将$start$更新成右端点的最大值
$DP$：
朴素：状态的设计不能有后效性，本题相关变量有牛数和区间长，
我们可以设计阶段为区间长，就有点类似$LIS$，不过我们求的是最小。
若是以牛为阶段，由于没有最优子结构性（这里也可以说不满足无后效性），所以不行。
那么我们按照区间的左端点排序(令子结构最优，一般使用反证法来证明。)，然后对区间进行枚举，对于当前的区间 $[L, R]$ 有 $i ∈[L,R]$
转移方程为，$f(i) = min{f(i), f(j-1)+1 (a_{i}-1<=j<=b_{i}-1)}$ (令子结构最优，一般使用反证法来证明。)
只有被覆盖了的点才会被更新值，这可以从状态定义得出。
那我们就需要一个可以实现动态查询区间最大值和修改元素功能的数据结构。
优化：线段树。
这道题线段树有两种写法，一个是有区间修改无区间查询，一个是有区间查询无区间修改。
因为一个是只查询一个点就可以了，另一个是只修改一个点就可以了。
#include <bits/stdc++.h>
using namespace std;
const int N = 25010, M = 1e6 + 10, INF = 1e8;
int n, m;
struct Range
{
int l, r;
bool operator < (const Range &W) const
{
return r < W.r;
}
}range[N];
struct Node // 1~i覆盖的最小线段树
{
int l, r;
int v;
// TODO: 需要维护的信息和懒标记
}tr[M * 4];
void pushup(int u)
{
tr[u].v = min(tr[u << 1].v, tr[u << 1 | 1].v);
// TODO: 利用左右儿子信息维护当前节点的信息
}
void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, INF};
else
{
tr[u] = {l, r, INF};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
// pushup(u); 这里确保为最大值
}
}
void update(int u, int l, int r, int d)
{
if (tr[u].l >= l && tr[u].r <= r)
{
// TODO: 修改区间
tr[u].v = min(tr[u].v, d);
return;
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) update(u << 1, l, r, d);
if (r > mid) update(u << 1 | 1, l, r, d);
pushup(u);
}
}
int query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r)
{
return tr[u].v; // TODO 需要补充返回值
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
int res = INF;
if (l <= mid) res = query(u << 1, l, r);
if (r > mid) res = min(res, query(u << 1 | 1, l, r));
return res;
}
}
int main()
{
scanf("%d%d", &n, &m);
build(1, 0, m); // 算0是为了有起始阶段
for (int i = 1; i <= n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);
update(1, 0, 0, 0); // 初始化
sort(range + 1, range + 1 + n);
for (int i = 1; i <= n; i ++ )
{
int l = range[i].l, r = range[i].r;
int v = query(1, l - 1, r - 1) + 1;
update(1, r, r, v); // 下一个区间若不包含（合法的右端）就是无解
}
int res = query(1, m, m);
if (res == INF) puts("-1");
else printf("%d", res);
}
P2
与上面问题不同的是它有权值，但思想是等价的，
由于上一题没有后效性，这一题也不会有。
由前面最优推现在最优，时间复杂度 $O(nlogn)$
#include <bits/stdc++.h>
using namespace std;
const int N = 25010, M = 1e6 + 10, INF = 1e8;
int n, m, e;
struct Range
{
int l, r, v;
bool operator < (const Range &W) const
{
return r < W.r;
}
}range[N];
struct Node // 1~i覆盖的最小线段树
{
int l, r;
int v;
// TODO: 需要维护的信息和懒标记
}tr[M * 4];
void pushup(int u)
{
tr[u].v = min(tr[u << 1].v, tr[u << 1 | 1].v);
// TODO: 利用左右儿子信息维护当前节点的信息
}
void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, INF};
else
{
tr[u] = {l, r, INF};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
// pushup(u); 这里确保为最大值
}
}
void update(int u, int l, int r, int d)
{
if (tr[u].l >= l && tr[u].r <= r)
{
// TODO: 修改区间
tr[u].v = min(tr[u].v, d);
return;
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) update(u << 1, l, r, d);
if (r > mid) update(u << 1 | 1, l, r, d);
pushup(u);
}
}
int query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r)
{
return tr[u].v; // TODO 需要补充返回值
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
int res = INF;
if (l <= mid) res = query(u << 1, l, r);
if (r > mid) res = min(res, query(u << 1 | 1, l, r));
return res;
}
}
int main()
{
scanf("%d%d%d", &n, &m, &e);
build(1, m, e + 1);
for (int i = 1; i <= n; i ++ ) scanf("%d%d%d", &range[i].l, &range[i].r, &range[i].v);
update(1, m, m, 0); // 初始化
sort(range + 1, range + 1 + n);
for (int i = 1; i <= n; i ++ )
{
int l = range[i].l, r = range[i].r;
if (r + 1 <= m) continue;
int v = query(1, max(l, m), r) + range[i].v;
update(1, r + 1, r + 1, v); // 下一个区间若不包含（合法的右端）就是无解
}
int res = query(1, e + 1, e + 1);
if (res == INF) puts("-1");
else printf("%d", res);
}
P3
因为要求最长上升子序列，所以我们要加一个限制是以$a[i]$结尾，
这是为了便于比较，知道是否是上升子序列，这种添加限制的方式，是动态规划中常用的技巧，
对于难以解决的问题，多思考，它是由哪些地方转移过来的，想要转移得知道哪些信息，
然后再添加这些信息，最后做简化。
$DP:$
$f[i][j]$表示长度是$i$，以$a[j]$为结尾的递增序列数量，
转移方程，$f(i, j) = \sum_{k=1}^{j-1}sum{f(i-1, k(a[k] < a[i])}$
这就是一个储存了不同长度的 $LIS$。
本题需要一个求区间和且可以删改元素的数据结构。
优化：线段树
这里有两种写法，第一个是要对每一个$f[j]$维护一个树状数组，
另一个是调整顺序，算第$j$层只会用$j-1$层，所以只用一个树状数组。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
vector<int> v;
int find(int x)
{
return lower_bound(v.begin(), v.end(), x) - v.begin();
}
int n, m;
int tr[N][N];
void add(int tr[], int x, int c)
{
for(int i = x; i <= n; i += i & -i) tr[i] = (tr[i] + c) % mod;
}
int sum(int tr[], int x)
{
int res = 0;
for(int i = x; i; i -= i & -i) res = (res + tr[i]) % mod;
return res;
}
int a[N];
int f[N][N]; // 考虑以a[i]结尾的长度为j的方案数
int main()
{
int _;
scanf("%d", &_);
for (int T = 1; T <= _; T ++ )
{
v.clear();
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
v.push_back(a[i]);
}
v.push_back(-2e9);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
memset(tr, 0, sizeof tr);
for (int i = 1; i <= n; i ++ )
{
a[i] = find(a[i]);
f[i][1] = 1; // 边界
add(tr[1], a[i], 1); // 第一维是为了满足不同长度的计算
for (int j = 2; j <= m && j <= i; j ++ )
{
f[i][j] = sum(tr[j - 1], a[i] - 1); // 查询有多少 <= a[i]-1 的数
add(tr[j], a[i], f[i][j]); // 在a[i]处插入f[i][j]，即有f[i][j]个以a[i]结尾的数满足
}
}
int res = 0;
for (int i = 1; i <= n; i ++ ) res = (res + f[i][m]) % mod;
printf("Case #%d: %d\n", T, res);
}
return 0;
}
本题有一些有用的技巧，
1. 树状数组可以多开一维储存历史值，
2. 对于多阶段$DP$树状数组可以储存每一个阶段，且表示与状态数组设计相同的含义。
总结
可以用来快速查询区间最值、或有增删元素功能的数据结构都可以用到$DP$优化上。
单调队列优化DP
P1
朴素：所有前 $i$ 个木匠刷了前 $j$ 个木板的最大报酬。
我们需要枚举 $m$ 个木匠 $n$ 种木板的终点以及 $n$ 种起点。
优化思路：由于$l$是固定的，我们可以用单调队列$O(n)$计算一段的最大值，
寻找可以使价值最大的起点，$max{f(i-1, k) + (j - k) * p[i]} （0<=j-k<=l[i]）$
注意：本题要根据$s$排序，消除后效性。
#include <bits/stdc++.h>
using namespace std;
const int N = 16010, M = 110;
int n, m;
int l[M], p[M], s[M];
int q[N], f[M][N];
struct Cr{
int l, p, s;
bool operator < (const Cr &W) const
{
return s < W.s;
}
}Cr[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i ++ )
{
scanf("%d%d%d", &Cr[i].l, &Cr[i].p, &Cr[i].s);
}
sort(Cr + 1, Cr + m + 1);
for (int i = 1; i <= m; i ++ )
{
int hh = 0, tt = -1;
int l = Cr[i].l, p = Cr[i].p, s = Cr[i].s;
/*如果有两个木匠，一定要保证前面的木匠刷的木板都在下一个左边
不然后面的木匠就不能继续往后面刷木板，所以我们会对s排序*/
for (int j = 0; j <= n; j ++ )
{
f[i][j] = f[i-1][j];
if (j) f[i][j] = max(f[i][j], f[i][j-1]);
while (hh <= tt && q[hh] < j - l) hh ++;
if (j >= s && hh <= tt)
{
int k = q[hh];
f[i][j] = max(f[i][j], f[i-1][k] + (j-k) * p);
}
if (j < s)
{
// 去掉 j * p[i]
while (hh <= tt && f[i-1][q[tt]] - q[tt] * p <= f[i-1][j] - j * p) tt --;
q[ ++ tt] = j;
}
}
}
printf("%d", f[m][n]);
}
P2
朴素：本题是区间划分，最后一个不同点需要区间枚举，会达到 $O(n^2)$ 复杂度，
优化思路：比较显然的是，根据贪心，当 $\sum_{k=j}^iA_k>M$ 时，$j$ 可以作为划分点。
这并不完全正确，事实上，并不是只有这样的 $A_j$ 才会成为划分点，
这可以用单调队列维护，因为队头不一定是最优解所以还需要一个 $muktiset$。
可重集是去找下标删数，没有找到就不删，不然会$TLE$
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 7;
LL n, m;
LL a[N], k[N], f[N], q[N];
multiset<LL> S;
int main()
{
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; i++ )
{
scanf("%lld", &a[i]);
if (a[i] > m) {
puts("-1");
return 0;
}
}
LL hh = 0, tt = 0, sum = 0;
for (LL i = 1, j = 0; i <= n; i ++ )
{
sum += a[i];
while (j < i && sum > m) sum -= a[ ++ j];
k[i] = j; // 维护决策点 (]
}
for (int i = 1; i <= n; i ++ )
{
while (hh <= tt && q[hh] <= k[i]) // 出了决策点的范围
{
auto id = S.find(f[q[hh]] + a[q[hh + 1]]);
if (id != S.end()) S.erase(id); // 不符合要求的删掉
hh ++;
}
while (hh <= tt && a[q[tt]] <= a[i])
{
auto id = S.find(f[q[tt - 1]] + a[q[tt]]);
if (id != S.end()) S.erase(id); // 不是最大值，是错误的，所以要删
tt --;
}
// 队列内元素单调递减，为了去维护 f(j) + max(j+1<=k<=i){Ak}
// 我们以q[tt]为界进行划分，这是可能满足最优决策的另一个方案
if (hh <= tt) S.insert(f[q[tt]] + a[i]); // 新阶段的划分 a[q[tt]] > ...a[i]
q[ ++ tt] = i;
f[i] = f[k[i]] + a[q[hh]];
if (S.size()) f[i] = min(f[i], *S.begin());
}
printf("%lld", f[n]);
}
我们一开始的分析，并不完全正确，只能拿到 $75$ 分，这是因为可能的最优决策还有别的。
如果 $j$ 会成为新段的最大值，但不会超过限制，那么也可以作为划分依据。
这当然不一定是最优的，但确实是一个可能的最优方案，加入后判断即可。
事实上，这才是用$muktiset$的原因，队头是满足第一个条件的最优解。
P3
其中有很多偏移量，但区间长度固定，因为是相对关系，且增长为线性，
所以用前面元素所在位置减去自己所在位置，即 $[ )$ 类型的底顶关系，由于是枚举的容积，
所以 除完（是数量）后乘（是价值），计算价值。
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, V = 20010;
int n, m;
int v[N], w[N], s[N];
int f[2][V];
int q[V];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
{
scanf("%d%d%d", &v[i], &w[i], &s[i]);
}
for (int i = 1; i <= n; i ++ )
{
for (int r = 0; r < v[i]; r ++ )
{
int hh = 0, tt = -1;
for (int j = r; j <= m; j += v[i])
{
while (hh <= tt && j - q[hh] > s[i]*v[i]) hh ++;
while (hh <= tt && f[i-1 & 1][q[tt]] + (j-q[tt])/v[i]*w[i] <= f[i-1 & 1][j]) tt --;
q[ ++ tt] = j;
f[i&1][j] = f[i-1 & 1][q[hh]] + (j-q[hh])/v[i]*w[i];
}
}
}
printf("%d", f[n&1][m]);
}
总结
$STL$ 真的要记住判断边界呀，我都错好几次了。
