贪心 & dp
题单介绍
## 记在前面
如你所见，这个题单是我找的 25 个蓝题，为的就是提升我在 dp/贪心 这一方面的能力，为了 NOIP 能好一点，虽然很多也是看了题解的。
可是 NOIP 却寄了，原因就是 T1 没特判（1=→2=），T3 T4 dp 写不出来保龄，所以训练了个啥呢。。。（T2 确实出乎意料的 AC 了那又怎么样呢）那么，还是明年加油吧。
By the way，现在一些题难度发生了变化，比如我认为比较难（最难写）的那题确实升紫了。
## 正文
~~NOIP翻盘记，启动！！！~~
## [[ABC265F] Manhattan Cafe](https://www.luogu.com.cn/problem/AT_abc265_f)
设 $f_{i,sp,sq}$ 表示 $sp=\displaystyle\sum_{k=1}^{i}|p_k-r_k|$ ，$sq=\displaystyle\sum_{k=1}^{i}|q_k-r_k|$ 的合法方案数，那么可以得到 $f_{i,sp,sq}\gets \displaystyle\sum_r f_{i-1,sp-|p_i-r|,sq-|q_i-r|}$。当然这样的时间复杂度是 $O(nD^3)$ 的。还得继续优化。
```cpp
int L=max(p[i]-sp,q[i]-sq),R=min(p[i]+sp,q[i]+sq);
for(int r=L;r<=R;r++)
{
int wp=abs(p[i]-r),wq=abs(q[i]-r);
f[i][sp][sq]=inc(f[i][sp][sq],f[i-1][sp-wp][sq-wq]);
}
```
**暴力拆开绝对值，然后维护对角线的前缀和**，分成三种情况。（假设 $p_i\le q_i$）
- $r<p_i$：即 $sp-|p_i-r|=r+(sp-p_i),sq-|q_i-r|=r+(sq-q_i)$。就是一个往右上角走的对角线。
- $p_i\le r\le q_i$：即 $sp-|p_i-r|=-r+(sp+p_i),sq-|q_i-r|=r+(sq-q_i)$。就是一个往左上角走的对角线。（当 $q_i\le p_i$ 的时候是一个往右下角走的对角线）
- $q_i<r$：即 $sp-|p_i-r|=-r+(sp+p_i),sq-|q_i-r|=-r+(sp+q_i)$。是一个往右上角走的对角线。
~~但是很难写啊啊啊啊啊啊！~~ 写代码需要耐心，交代码也需要耐心。
```cpp
int CalcPos(int sx,int sy,int ex,int ey){return sx>ex?0:dec(kpos[ex][ey],(sx>0&&sy>0)?kpos[sx-1][sy-1]:0);}
int CalcNeg(int sx,int sy,int ex,int ey){return sx>ex?0:dec(kneg[ex][ey],(sx>0&&sy<d)?kneg[sx-1][sy+1]:0);}
void maintain()
{
memset(kpos,0,sizeof(kpos));memset(kneg,0,sizeof(kneg));
for(int sp=0;sp<=d;sp++)
for(int sq=0;sq<=d;sq++)
if(sp>0&&sq>0)kpos[sp][sq]=inc(kpos[sp-1][sq-1],res);
else kpos[sp][sq]=res;
for(int sp=0;sp<=d;sp++)
for(int sq=d;sq>=0;sq--)
if(sp>0&&sq<d)kneg[sp][sq]=inc(kneg[sp-1][sq+1],res);
else kneg[sp][sq]=res;
}
```
```cpp
int L=max(p[i]-sp,q[i]-sq),R=min(p[i]+sp,q[i]+sq);
if(L>R)continue;
int mn=min(p[i],q[i]),mx=max(p[i],q[i]);
int sx,sy,ex,ey;
if(L<mn)
{
sx=L+(sp-p[i]);sy=L+(sq-q[i]);
ex=min(mn-1,R)+(sp-p[i]);ey=min(mn-1,R)+(sq-q[i]);
res=inc(res,CalcPos(sx,sy,ex,ey));
}
if(p[i]<=q[i])
{
sx=-min(R,mx)+(sp+p[i]);sy=min(R,mx)+(sq-q[i]);
ex=-max(L,mn)+(sp+p[i]);ey=max(L,mn)+(sq-q[i]);
}
else
{
sx=max(L,mn)+(sp-p[i]);sy=-max(L,mn)+(sq+q[i]);
ex=min(R,mx)+(sp-p[i]);ey=-min(R,mx)+(sq+q[i]);
}
res=inc(res,CalcNeg(sx,sy,ex,ey));
if(mx<R)
{
sx=-R+(sp+p[i]);sy=-R+(sq+q[i]);
ex=-max(mx+1,L)+(sp+p[i]);ey=-max(mx+1,L)+(sq+q[i]);
res=inc(res,CalcPos(sx,sy,ex,ey));
}
```
话说为什么[大佬的代码](https://atcoder.jp/contests/abc265/submissions/46484200)可以做到这么短？！
## [AT_dp_t Permutation](https://www.luogu.com.cn/problem/AT_dp_t)
设 $f_{i,j}$ 表示前 $i$ 个中填了 $1\sim i$，且最后一个为 $j$ 的方案数。那么假设第 $i-1$ 个为 $k$，就可以得到以下转移方程：
$$
f_{i,j}=
\begin{cases}
\displaystyle\sum_{k=1}^{j-1}f_{i-1,k} & <
\\
\\
\displaystyle\sum_{k=j}^{i-1}f_{i-1,k} & >
\end{cases}
$$
稍微解释以下，为什么可以这样转移。将 $j$ 从 $[1,i]$ 中拿出，剩下的 $i-1$ 个数同样互不相同。于是可以**建立一个向排名的映射**，$i\to {\rm rank}(i)$，发现后者正好是一个 $i-1$ 的序列，于是便对应了 $f_{i-1,{\rm rank}(k)}$ 这种方案了。这时再分类讨论 `<` 和 `>` 的情况，我们发现删掉一个 $j$ 之后，`<` 的情况中，${\rm rank}(k)\in [1,j-1]$，同理可得当 `>` 的时候，${\rm rank}(k)\in [j,i-1]$，即可得到这样的转移方程。时间复杂度 $O(n^3)$，用前缀和优化轻松做到 $O(n^2)$。
```cpp
if(a[i-1]=='<')f[i][j]=s[i-1][j-1];
else f[i][j]=dec(s[i-1][i-1],s[i-1][j-1]);
s[i][j]=inc(s[i][j-1],f[i][j]);
/*
if(a[i-1]=='<')for(int k=1;k<j;k++)f[i][j]=in(f[i][j],f[i-1][k]);
else for(int k=j;k<i;k++)f[i][j]=inc(f[i][j],f[i-1][k]);
*/
```
## [CF1582F2 Korney Korneevich and XOR (hard version)](https://www.luogu.com.cn/problem/CF1582F2)
不知道是我太 sb 了还是什么鬼，贺都差点没贺懂。
先分析弱化版。
下面 $\oplus$ 表示按位异或。
设 $f_{i,sta}$ 表示选取的最后一个**位置**是 $i$，异或和为 $sta$ 的这种方案是否合法，考虑如何转移。显然，当 $j<i$ 且 $a_j<a_i$ 的时候可以从 $j\to i$，即 `f[i][sta]|=f[j][sta^a[i]];`。时间复杂度 $O(n^2A)$。（实际上我们发现只有 $A^2$ 个状态会有用，而没有必要去记录 $a_i$ 具体是哪个 $i$，将**位置**改成**数**可以减少状态，所以就是 $O(nA^2)$，感觉应该可以加一个 bitset 进行优化然后通过？）
但是对于每一个 $i$ 都尝试去枚举 $j$ 那未免也太不划算了。我们发现，假如 $j_1<j_2$，且两者都能到达 $sta\oplus a_i$ 的状态，那么我们会发现 $j_1$ 更容易贡献。这就好办了，那我们记录对于每一个状态 $sta$，所有能到达这个状态的 $a_j$ 的最小值即可。由于是按顺序枚举，所以说 $j<i$ 的条件是保证成立的。注意别忘记 $[]$ 的情况。时间复杂度 $O(nA)$。
```cpp
for(int i=1;i<=n;i++)
{
mn[a[i]]=min(mn[a[i]],a[i]);t[a[i]]=1;
for(int sta=0;sta<(1<<9);sta++)if(mn[(sta^a[i])]<a[i])t[sta]=1,mn[sta]=min(mn[sta],a[i]);
}
```
接着，强化版。
但是前面好像不太好优化了？那么换个方向考虑，即将原来的思路 $j\to i$ 变成 $i\to j$。$f_{a_i,sta}$ 表示最后一个**数**是 $a_i$，异或和为 $sta$ 的这种状态是否合法。
我们发现，$(a_i,sta)\to (a_j,sta\oplus a_i)\quad(a_j\in (a_i,A])$。**但是时间复杂度不理想，在这题是因为贡献次数过多**。实际上对于相同的 $sta\oplus a_i$ ，转移的 $a_j$ 没有必要每一次都从 $a_i$ 开始枚举到 $A$，因为若 $f_{a_j,sta\oplus a_i}$ 已经被贡献为 $1$，那么显然对于 $a_j'>a_j$，$f_{a_j',sta\oplus a_i}$ 同样也已经被贡献为了 $1$。所以可以记录一个 $mx_{sta}$ 表示这个状态下的未贡献到的最小值，只需要 $v\in (a_i,mx_{sta\oplus a_i}]$，然后再更新 $mx$ 的值即可。而对于每一个 $a$，用一个 vector 记录合法的 $sta$，初始时所有 $sta$ 的合法状态都只有 $0$。
分析时间复杂度，每一个 vector 最多只会有 $A$ 个数，又只有 $A$ 个 vector，故时间复杂度 $O(n+A^2)$。
```cpp
for(int i=1;i<(1<<13);i++)vec[i].push_back(0),mx[i]=(1<<13)-1;
for(int i=1;i<=n;i++)
{
int a=read();
for(int it:vec[a])
{
int v=it^a;t[v]=1;
while(mx[v]>a)vec[mx[v]--].push_back(v);
}
vec[a].clear();
}
```
## [UVA10891 Game of Sum](https://www.luogu.com.cn/problem/UVA10891)
感觉很经典啊，直接 dp 做个 $O(n^2)$ 就完了是吧。再一看，取**任意数量**的数，诶好像不太对。仔细一想，不还是一个区间 dp 吗？设 $f_{i,j}$ 表示在 $[i,j]$ 中，先手可以取得的最大值。那么先手取完一个区间后，肯定让剩下那个区间 $[i',j']$ 的价值尽可能小，这样才能保证自己取得比别人更多。对于另一个人，同样的道理，注意还可以取完，于是就有以下转移方程
$$f_{i,j}=sum(i,j)=\min\{0,f_{i+1,j},f_{i+2,j},\cdots,f_{j,j},f_{i,j-1},f_{i,j-2},\cdots,f_{i,i}\}$$
这样就是 $O(n^3)$，可以通过此题。
```cpp
int j=i+len-1,mn=0;
for(int k=i;k<j;k++)mn=min(mn,f[i][k]);
for(int k=i+1;k<=j;k++)mn=min(mn,f[k][j]);
f[i][j]=s[j]-s[i-1]-mn;
```
但是我们还是感觉太慢了怎么办，当然还可以继续优化啦，设 $l_{i,j}=\displaystyle\min_{k=i}^j f_{i,k}$，$r_{i,j}=\displaystyle\min_{k=i}^j f_{k,j}$，然后边做边更新 $l_{i,j}$ 和 $r_{i,j}$，就可以做到 $O(n^2)$ 啦。
```cpp
int j=i+len-1;
f[i][j]=s[j]-s[i-1]-min(0,min(l[i][j-1],r[i+1][j]));
l[i][j]=min(l[i][j-1],f[i][j]);r[i][j]=min(r[i+1][j],f[i][j]);
```
## [UVA12983 The Battle of Chibi](https://www.luogu.com.cn/problem/UVA12983)
比较明显的 dp。设 $f_{i,j}$ 表示以 $i$ 为结尾，长度为 $j$ 的上升子序列个数。那么就有 $f_{i,j}=\displaystyle\sum_{k<i,a_k<a_i}f_{k,j-1}$。时间复杂度 $O(n^3)$。
```cpp
memset(f,0,sizeof(f));f[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
for(int k=0;k<i;k++)
if(a[k]<a[i])f[i][j]=inc(f[i][j],f[k][j-1]);
for(int i=m;i<=n;i++)ans=inc(ans,f[i][m]);
```
考虑如何优化，发现就是求一个顺序对。那么就可以使用一个数据结构做这个东西，然后时间复杂度就变成了 $O(n^2\log n)$，还是挺简单的。树状数组好写，并且常数更小，就决定是你啦！~~另外听说这道题线段树会被卡常？~~
实测确实卡常，注意清空是使用 `memset()` 而非单点撤销，因为操作的数量也达到了 $O(n^2)$ 的级别，单点操作反而还多了个 $\log$，其次别习惯开了线段树的大小，这样也会增加 `memset()` 的时间开销。。。
```cpp
for(int i=1;i<=n;i++)Tree[i].clear();
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
f[i][j]=inc(f[0][j-1],Tree[j-1].ask(a[i]-1)),
Tree[j].add(a[i],f[i][j]);
for(int i=m;i<=n;i++)ans=inc(ans,f[i][m]);
```
## [[AGC057B] 2A + x](https://www.luogu.com.cn/problem/AT_agc057_b)
考虑到如果对于一个 $a_i$ 进行 $k$ 次操作，那么 $a_i$ 最后会变成 $[L_i,R_i]$ 区间中的一个数，其中 $L_i=2^k a_i$，$R_i=L_i+(2^{k-1}-1)x$。下面假设每个数已经分配好了操作的次数，我们发现一个大体思路就是，选择一些大的数往 $L$ 这个方向走，一些小的数往 $R$ 这个方向走，这样似乎会让答案变小。那么答案就变成了 $\max(0,\displaystyle\max_{i=1}^n L_i-\displaystyle\min_{i=1}^n R_i)$，注意这里有 $0$ 是因为考虑到答案本身就有 $\ge 0$ 的性质。
思考如何让答案变小，发现每次操作之后，$\max L$ 和 $\min R$ 都会单调不降，所以可以每次贪心的选取最小的 $R$ 进行操作，就肯定会让 $\min R$ 更大（答案变小），而 $\max L$ 有可能变大，有可能不变。由于操作顺序不影响答案，所以说 $\max L$ 在后面该变大还是得变大，所以贪心得证。
答案在 $\min R$ 爆 `long long` 之前取到最优解，这个暂时不想 ~~不会~~ 证。
```cpp
for(int i=1;i<=n;i++)maxl=max(maxl,a[i]=read()),q.push((data){a[i],a[i]});
while(ans>0)
{
data t=q.top();q.pop();
if(t.r>inf)break;
ans=min(ans,maxl-t.r);maxl=max(maxl,t.l*2);
q.push((data){t.l*2,t.r*2+x});
}
printf("%lld",max(0ll,ans));
```
## [AT_dp_y Grid 2](https://www.luogu.com.cn/problem/AT_dp_y)
感觉挺难的。
首先考虑如果没有任何障碍物，那么就有 $f_{i,j}=f_{i-1,j}+f_{i,j-1}$，发现这式子和组合数是一样的。从另一个角度，由于从 $(1,1)$ 走到 $(n,m)$ 需要走 $n-1$ 个下和 $m-1$ 个上，就是组合数 $\dbinom{n+m-2}{n-1}$（或者写成 $C_{n+m-2}^{n-1}$）所以设 ${\rm calc}(i,j)$ 表示从第 $j$ 个点到第 $i$ 个的路径（这里不考虑中间的障碍物），简单得到 ${\rm calc}(i,j)=\dbinom{(x_i-x_j)+(y_i-y_j)}{(x_i-x_j)}$。
现在把障碍物算上，最简单的方法就是总方案减去不合法的方案，即容斥。设 $f_i$ 表示从 $(1,1)$ 走到第 $i$ 个点的合法路径，那么有容斥
$$f_i={\rm calc}(i,0)-\sum {\rm calc}(i,j)\times {\rm calc}(j,0)+\sum {\rm calc}(i,j)\times {\rm calc}(j,k)\times {\rm calc}(k,0)-\cdots$$
但是要是直接容斥显然不行，得使用一点工具解决，这里就转化成
$$f_i={\rm calc}(i,0)-\sum_{x_j\le x_i,y_j\le y_i} f_j\times {\rm calc}(i,j)$$
个人感觉理解了 **SOS dp** 再去理解这个似乎更加容易。（蒟蒻水平过低，也说不清这东西像什么）
## [CF940E Cashback](https://www.luogu.com.cn/problem/CF940E)
糅合了贪心的 dp？反正很难想到。
感觉不好快速的找到前 $\lfloor\dfrac{k}{c}\rfloor$ 小的值，考虑一下有什么性质。手玩一下发现了这些性质：
- $1\le k<c$，此时 $\lfloor\dfrac{k}{c}\rfloor=0$，那么答案就是整个区间的和，这样和直接拆成 $k$ 个长度为 $1$ 的区间的答案是相同的。
- $k=c$，此时 $\lfloor\dfrac{k}{c}\rfloor=1$，答案就是区间和减去最小值。
- $k>c$，口胡一下这个东西不可能分成两个长度为 $c$ 和 $k-c$ 的区间更优。发现 $\lfloor\dfrac{c}{c}\rfloor+\lfloor\dfrac{k-c}{c}\rfloor=\lfloor\dfrac{k}{c}\rfloor$，所以两者取的数的数量是一样的。又发现分成两个区间之后显然是比原来整个区间取的最小值之和更大的（或者等于），所以得证。
显然如果 $k-c$ 仍然比 $c$ 大，那么同理可以继续分解。那么将会分成若干个长度为 $c$ 的区间和剩余一个长度 $<c$ 的区间。于是，这道题就可以转化为 只能分解成长度为 $1$ 和 $c$ 的区间了。接下来就到 dp 登场了。
设 $f_i$ 表示考虑到第 $i$ 个数时的最小答案。那么可以有以下转移
$$
f_i=\begin{cases}f_{i-1}+a_i\\f_{i-c}+\displaystyle\sum_{j=i-c+1}^ia_j-\displaystyle\min_{j=i-c+1}^i a_j & (i\ge c)\end{cases}
$$
$\sum$ 这个使用前缀和预处理，$\min$ 这个使用单调队列预处理，最后时间复杂度为 $O(n)$。
```cpp
for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
for(int i=1;i<=n;i++)
{
while(h<=t&&q[h]<=i-c)h++;
while(h<=t&&a[q[t]]>a[i])t--;
q[++t]=i;mn[i]=a[q[h]];
}
for(int i=1;i<c;i++)f[i]=f[i-1]+a[i];
for(int i=c;i<=n;i++)f[i]=min(f[i-1]+a[i],f[i-c]+(s[i]-s[i-c])-mn[i]);
printf("%lld",f[n]);
```
## [UVA1344 Tian Ji -- The Horse Racing（田忌赛马）](https://www.luogu.com.cn/problem/UVA1344)
dp 方法也行，但是贪心更强，而且感觉应该是经典的贪心？所以记录一下贪心策略。
- 田忌最强马 > 齐王最强马：能比就比，获得 $200$。
- 田忌最强马 < 齐王最强马：打消耗，拿最弱的和齐王最强的比，必输 $200$。
- 田忌最弱马 > 田忌最弱马：能比就比（因为和更强的比也不一定比得过），获得 $200$。
- 其他：打消耗，直接拿田忌最弱马和齐王最强马比。（注意这里，田忌最弱马也有可能和齐王最强马平局）
```cpp
ha=hb=1;ta=tb=n;
for(int i=1;i<=n;i++)a[i]=read();sort(a+1,a+1+n);
for(int i=1;i<=n;i++)b[i]=read();sort(b+1,b+1+n);
for(int i=1;i<=n;i++)
{
if(a[ta]>b[tb]){ta--;tb--;ans+=200;continue;}
if(a[ta]<b[tb]){ha++;tb--;ans-=200;continue;}
if(a[ha]>b[hb]){ha++;hb++;ans+=200;continue;}
if(a[ha]<b[tb])ans-=200;ha++;tb--;
}
printf("%d\n",ans);
```
## [[ABC318F] Octopus](https://www.luogu.com.cn/problem/AT_abc318_f)
首先考虑如何判断某个位置是否合法，显然就是贪心的将手臂长度排序，短的选更近的，长的选更远的。判断的时间复杂度为 $O(n\log n)$。但是如果每个点都枚举一遍肯定超时的，思考如何优化。
考虑划分成若干个区间，如果这个区间的端点可以，那么整个区间都可以。划分的端点大概率和 **坐标 $x$** 和 **手臂长度 $l$** 有关，下面证明一下。
假设当前划分的界限为 $k$，存在两种情况：
- $k$ 合法而 $k+1$ 不合法（右端点），那么必须存在 $(x_i,l_j)$ 满足 $k-l_j\le x_i\le k+l_j$，而不满足 $k+1-l_j\le x_i\le k+1+l_j$，解得 $k=x_i+l_j$。
- $k$ 不合法而 $k+1$ 合法（左端点），同理可得满足 $k+1-l_j\le x_i\le k+l_j$，而不满足 $k-l_j\le x_i\le k+l_j$，解得 $k=x_i-l_j-1$。
如果考场上实在懒得想这么多，可以直接把所有 $x_i+l_j$ 和 $x_i-l_j$ 及其左右端点全部判断一遍，这里看到[ Register int 的做法](https://www.luogu.com.cn/blog/const1e7/at-abc318-f-soltuion)。
于是只有 $O(n^2)$ 个界限，所以最终的时间复杂度为 $O(n^3\log n)$。
```cpp
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
s[++tot]=x[i]-l[j]-1,s[++tot]=x[i]+l[j];
sort(s+1,s+tot+1);
for(int i=2;i<=tot;i++)
if(check(s[i]))ans+=s[i]-s[i-1];
```
## [[AGC008D] K-th K](https://www.luogu.com.cn/problem/AT_agc008_d)
一个构造题。~~纵所周知构造题是最 sb 的。~~
分析题目即可得到要求我们满足 $[1,X_i)$ 这里需要有 $i-1$ 个 $i$，同理 $(X_i,n]$ 这里需要有 $n-i$ 个 $i$。
首先先暴力填完输入的 $X_i$。对于情况 $[1,X_i)$，我们可以贪心的选择 $X_i$ 更小的那个去放 $i$，因为他比其他数更加需要先被填，如果此时没有多余的空位了，那么就输出无解。对于 $(X_i,n]$ 同理。
```cpp
for(int i=1;i<=n;i++)d[i]=(node){read(),i},a[d[i].x]=i;
sort(d+1,d+1+n,cmp);
for(int i=1;i<=n*n;i++)s[i]=s[i-1]+(a[i]==0);
for(int i=1;i<=n;i++)
{
sum+=d[i].id-1;num=0;
if(s[d[i].x]<sum)return (void)printf("No"),0;
while(num<d[i].id-1){p++;if(!a[p])a[p]=d[i].id,num++;}
}
sum=0;p=n*n+1;
for(int i=n*n;i;i--)s[i]=s[i+1]+(a[i]==0);
for(int i=n;i;i--)
{
sum+=(n-d[i].id);num=0;
if(s[d[i].x]<sum)return (void)printf("No"),0;
while(num<n-d[i].id){p--;if(!a[p])a[p]=d[i].id,num++;}
}
printf("Yes\n");
for(int i=1;i<=n*n;i++)printf("%d ",a[i]);
```
## [AT_dp_x Tower](https://www.luogu.com.cn/problem/AT_dp_x)
0/1 背包，但是直接做 $n$ 次显然是不行的。考虑如何优化。下面贪心选择一些交换，使得更优一点（即 `exchange arguments`，[更多的此类技巧点击这里](https://ouuan.github.io/post/%E6%B5%85%E8%B0%88%E9%82%BB%E9%A1%B9%E4%BA%A4%E6%8D%A2%E6%8E%92%E5%BA%8F%E7%9A%84%E5%BA%94%E7%94%A8%E4%BB%A5%E5%8F%8A%E9%9C%80%E8%A6%81%E6%B3%A8%E6%84%8F%E7%9A%84%E9%97%AE%E9%A2%98/)）对于 $i$ 和 $j$ 考虑哪一个放在下面更优一点。显然将两种摆放方式的剩余的载重比较一下，若剩余的更多，那么放在下面就更优，即若 $j$ 放下面优于 $i$，则 $s_i-w_j<s_j-w_i$，把相同变量放到一起得到 $s_i+w_i<s_j+w_j$，然后以这个为排序基准，做 1 次 0/1 背包即可。
```cpp
struct node{ll w,s,v;}d[N];
bool cmp(node A,node B){return A.w+A.s<B.w+B.s;}
```
```cpp
sort(d+1,d+1+n,cmp);
for(int i=1;i<=n;i++)
for(int j=d[i].w+d[i].s;j>=d[i].w;j--)
f[j]=max(f[j],f[j-d[i].w]+d[i].v);
for(int i=0;i<=V-5;i++)ans=max(ans,f[i]);
```
## [CF10D LCIS](https://www.luogu.com.cn/problem/CF10D)
结合了 LIS 和 LCS 的 dp，所以首先我们复习一下 LIS 和 LCS 是如何写的。
#### LIS
设 $f_i$ 表示以 $i$ 为结尾的 LIS，可以得到转移方程为 $f_i=\max f_j+1 \quad (a_j<a_i)$。
#### LCS
设 $f_{i,j}$ 表示 $a$ 中考虑了前 $i$ 个，$b$ 中考虑了前 $j$ 个的 LCS。可以得到转移方程为
$$f_{i,j}=\max\begin{cases}f_{i-1,j}\\f_{i,j-1}\\f_{i-1,j-1}+1 & (a_i=b_j)\end{cases}$$
#### LCIS
结合一下这两个东西，设 $f_{i,j}$ 表示 $a$ 中考虑了前 $i$ 个，并且结尾为 $b_j$ 的 LCIS，有以下情况：
- $a_i\ne b_j$，不能选择 $a_i$，答案为 $f_{i-1,j}$。
- $a_i=b_j$ 可以选择 $a_i$，枚举找到一个合法的 $k$ 满足 $k<j,b_k<b_j$，这时答案为 $\max f_{i-1,k}+1$。
于是最后记录以下每个答案的前驱就可以知道具体的 LCIS 是什么了。
```cpp
a[0]=b[0]=-1;//注意这里
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i]==b[j])
{
for(int k=0;k<j;k++)
if(a[i]>b[k]&&f[i][j]<f[i-1][k]+1)
f[i][j]=f[i-1][k]+1,p[i][j]=k;
}
else f[i][j]=f[i-1][j],p[i][j]=p[i-1][j];
}
}
for(int i=1;i<=m;i++)
if(f[n][id]<f[n][i])id=i;
printf("%d\n",f[n][id]);
for(;id;id=p[n][id])st[++t]=b[id];
for(int i=t;i;i--)printf("%d ",st[i]);
```
## [[AGC018B] Sports Festival](https://www.luogu.com.cn/problem/AT_agc018_b)
最简单的一题。
考虑先全部选择，然后贪心 ban 掉最大那个，然后就做完了。。。
时间复杂度为 $O(nm)$。
```cpp
for(int i=1;i<=n;i++)p[i]=1;
while(1)
{
memset(t,0,sizeof(t));id=0;
for(int i=1,c;i<=n;i++)
{
c=a[i][p[i]];
while(vis[c])c=a[i][++p[i]];
if(p[i]>m)continue;
t[c]++;
if(t[id]<t[c])id=c;
}
if(!id)break;
ans=min(ans,t[id]);vis[id]=1;
}
```
## [P4161 [SCOI2009] 游戏](https://www.luogu.com.cn/problem/P4161)
这道题最难的部分还不是 dp，是如何转化成最 naive 的背包。
首先可以发现，如果答案应该是环的长度的 $\rm lcm$。所以就是计算最后有多少种 $\rm lcm$。又发现，可以只考虑**不同质数的幂** $p^k$ 和 $1$ 作为选取的数，这样会使得表示的 $\rm lcm$ 更多。这是为什么呢，假如说选取了 $15$，但是和 $3,5,1_{\times 7}$ 两个数的 $\rm lcm$ 一样，而 $3+5<15$，这说明后者可以有更多的空间表示。
处理完之后，题目就变成了一个背包问题了。然后这里就很简单 AC 了。
```cpp
for(int i=1;i<=tot;i++)
for(int j=n;j>=p[i];j--)
for(int k=p[i];k<=j;k*=p[i])
f[j]+=f[j-k];
for(int i=0;i<=n;i++)ans+=f[i];
```
## [P6564 [POI2007] 堆积木KLO](https://www.luogu.com.cn/problem/P6564)
考虑 dp，容易想到设 $f_{i,j}$ 表示前 $i$ 个积木删除 $j$ 个的最大值，则可以得到递推方程
$$f_{i,j}=\max (f_{i-1,j}+[a_i=i-j],f_{i-1,j-1})$$
时间复杂度 $O(n^2)$。
但是发现不好优化，考虑重新设计状态。设 $f_i$ 表示第 $i$ 个积木归位的最优解。思考有哪些 $j$ 可以转移给 $i$，需要满足 $j<i$，$a_j<a_i$，$a_i-a_j\le i-j$。进一步发现如果满足后面两个，那么必然满足第一个，同时将 $a_i-a_j\le i-j$ 变成 $a_j-j\ge a_i-i$ 并以这个为关键字排序。
```cpp
bool cmp(data A,data B){return (A.w-A.id!=B.w-B.id)?A.w-A.id>B.w-B.id:A.id<B.id;}
```
排序之后，只需要满足 $a_j<a_i$ 即可，这里使用树状数组维护，时间复杂度 $O(n\log n)$。
```cpp
for(int i=1;i<=n;i++)
{
if(d[i].id<d[i].w)continue;
f[d[i].id]=Tree.ask(d[i].w-1)+1;
Tree.upd(d[i].w,f[d[i].id]);
ans=max(ans,f[d[i].id]);
}
```
有个[双倍经验](https://www.luogu.com.cn/problem/CF1575L)。
## [P3147 [USACO16OPEN] 262144 P](https://www.luogu.com.cn/problem/P3147)
区间 dp，有个 Easy Version 的绿题。
我们以前写区间 dp 都是设 $f_{i,j}$ 表示 $[i,j]$ 区间的一些信息，但是这题这样设就寄了。看到这道题，我们发现合并出一个 $i$，只需要两个可以合并出 $i-1$ 并且相邻的区间即可，而我们发现，这个值只有 $58$ 的大小，这启发我们往这个方向思考。
设 $f_{i,j}$ 表示以 $j$ 为左端点，可以合并出 $i$ 的区间的右端点（左闭右开），即 $[j,f_{i,j})$ 可以合并出 $i$，显然从两个 $i-1$ 合并得到，即 $f_{i,j}=f_{i-1,f_{i-1,j}}$，如果不能合并，就为 $0$。这其实有点像倍增。时间复杂度为 $O(n)$，带个 $58$ 的常数（也可以认为是 $O(n\log n)$）。
```cpp
for(int i=1;i<=n;i++)f[a[i]][i]=i+1;
for(int i=1;i<=58;i++)
{
for(int j=1;j<=n;j++)
{
if(!f[i][j])f[i][j]=f[i-1][f[i-1][j]];
if(f[i][j])ans=i;
}
}
```
## [P3845 [TJOI2007] 球赛](https://www.luogu.com.cn/problem/P3845)
挺简单的，首先一眼看出来发现要先分类，然后排个序，题目要求我们求最少的上升子序列的个数，又有 $\text{Dilworth}$ 定理得到，相当于求最长下降子序列的长度，于是这题就做完了。这里使用的是 $O(n^2)$ 的做法，当然还有 $O(n\log n)$ 的做法，但是太懒了。
```cpp
bool cmp(data A,data B){return A.x!=B.x?A.x<B.x:A.y<B.y;}
void solve()
{
n=read();ans=0;
for(int i=1;i<=n;i++)
{
scanf("%d-%d",&d[i].x,&d[i].y);
if(d[i].x>d[i].y)swap(d[i].x,d[i].y);
}
sort(d+1,d+1+n,cmp);
for(int i=1;i<=n;i++)
{
f[i]=1;
for(int j=1;j<i;j++)
if(d[j].y>d[i].y)f[i]=max(f[i],f[j]+1);
ans=max(ans,f[i]);
}
printf("%d\n",ans);
}
```
## [P4945 最后的战役](https://www.luogu.com.cn/problem/P4945)
这题 dp 还是很典啊。
首先观察题目，我们发现对于操作 1,2，在第 $i$ 秒取多少并不会对其他秒产生影响，也就是说，我们可以预处理出来一个 $val_i$ 表示在第 $i$ 秒这个时刻，操作 1,2 能取到的最大的价值。接着考虑加上操作 3 的 dp，设 $f_{i,j}$ 表示前 $i$ 秒使用了 $j$ 次双倍，则可以得到转移方程：
$$f_{i,j}=\max(f_{i-1,j}+val_i,f_{i-2,j}+val_i\times 2)$$
时间复杂度是 $O(nm)$，空间如果滚动的话可以做到 $O(m)$。
```cpp
f[1][0]=val[1];
for(int i=2;i<=n;i++)
{
f[i][0]=f[i-1][0]+val[i];
for(int j=1;j<=m;j++)
f[i][j]=max(f[i-1][j]+val[i],f[i-2][j-1]+val[i]*2);
}
for(int i=0;i<=m;i++)ans=max(ans,f[n][i]);
```
但是这题还有一个更好做的方法，就是反悔贪心。
我们发现，如果一次双倍都不选取的话，那么答案应该就是 $\displaystyle\sum_{i=1}^n val_i$，如果让 $i$ 双倍，那么得到的价值就是 $val_{i+1}-val_{i}$。我们设其为 $t_i$，所以就将题目转化为了选出 $m$ 个不相邻的 $t_i$，使其最大。
有人可能认为这里的贪心就是选取一个最大的，然后把两边的打标记，这是不可行的，例如 `8 9 8 1`。正确的做法是取最大的，然后有一步反悔的操作，是取最大的旁边两个而不取最大的这个。具体这样操作，取出来一个数 $a_i$ 先累加到答案中，然后把 $i-1,i,i+1$ 合并（值为 $a_{i-1}+a_{i+1}-a_i$）为一个整体，表示反悔的操作（所以说 $a_{i-1},a_{i+1}$ 其实并不是编号 -1,+1 的数，而是这个整体的左边和右边的数）注意合并之后需要打个标记，否则可能会取出来原来旁边这个。
```cpp
for(int i=1;i<=n;i++)lnk(i-1,i),lnk(i,i+1);
while(m--)
{
while(!q.empty())if(vis[q.top().id])q.pop();else break;
if(q.empty())break;
data d=q.top();q.pop();int l=pre[d.id],r=nxt[d.id];
ans=max(ans,sum+=d.w);
lnk(pre[l],d.id);lnk(d.id,nxt[r]);vis[l]=vis[r]=1;
q.push((data){d.id,t[d.id]=t[l]+t[r]-d.w});
}
```
贪心解法的多倍经验：[[ABC162F] Select Half](https://www.luogu.com.cn/problem/AT_abc162_f) + [P1484 种树](https://www.luogu.com.cn/problem/P1484) + [P1792 [国家集训队] 种树](https://www.luogu.com.cn/problem/P1792) + [P3620 [APIO/CTSC2007] 数据备份](https://www.luogu.com.cn/problem/P3620) + [Guard Duty (medium)](https://www.luogu.com.cn/problem/CF958E2)
## [CF1680D Dog Walking](https://www.luogu.com.cn/problem/CF1680D)
题面有点劣，我们转化一下。首先可以将 $a=0$ 地方改成 $[-k,k]$ 的任何一个值（当然也可以改回 $0$），然后设 $s$ 为 $a$ 的前缀和数组，要求满足 $s_n=0$，求 $\max s_i-\min s_i$ 的最大值。
首先特判掉无解的情况，即如果将所有的 $0$ 都取了 $k$ 后，$s_n<0$，那么无解；同理都取了 $-k$ 之后，$s_n>0$ 也无解，接下来考虑如何构造一个合法的方案。
我们发现，如果先不考虑 $s_n=0$ 的限制的话，显然是全部取 $k$ 或者 $-k$ 可以取到最大值。加入 $s_n=0$ 的这个限制，设选择的区间为 $[i,j]$，分选取 $k$ 和 $-k$ 两种情况。当选 $k$ 的时候，我们发现 $[1,i)$ 和 $(j,n]$ 这两个部分的尽可能选取更多的 $-k$ 来中和才能保证最后的 $s_n=0$。对于选取 $-k$ 的情况也同理。于是就可以枚举左右端点 $O(n^2)$ 完成这题了。
```cpp
n=read();k=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
t[i]=t[i-1]+(!a[i]);
s[i]=s[i-1]+a[i];
}
if(abs(s[n])>k*t[n])return printf("-1"),0;
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
ll sum1=s[j]-s[i-1],num1=t[j]-t[i-1];
ll sum2=s[n]-sum1,num2=t[n]-num1;
ans=max(ans,min(abs(sum1+num1*k),abs(sum2-num2*k)));
ans=max(ans,min(abs(sum1-num1*k),abs(sum2+num2*k)));
}
}
printf("%lld",ans+1);
```
## [P3942 将军令](https://www.luogu.com.cn/problem/P3942)
又是糅合了贪心的 dp？！不过贪心似乎也没有那么难想。贪心策略很简单，如果当前还不需要设置驻点，那么就可以尽可能往上设置。
下面考虑 dp 如何写。设 $f_u$ 表示 $u$ 子树内与 $u$ 最近的驻点，$g_u$ 表示最远的未控制点。转移很简单，$f_u=\min f_v+1$，$g_u=\max g_v+1$。
- 当 $g_u=k$，那么这个时候必须设置当前的 $u$ 点为驻点了，否则就控制不到那个点了，所以 $f_u\gets 0$，$g_u\gets -1$ 表示这个点是驻点。
- 如果 $f_u+g_u\le k$，那么表示 $u$ 点也会被控制到，所以 $g_u\gets-1$ 表示这个点被控制了。
注意特判根节点，因为根节点这个位置已经不可以再上移了。
```cpp
void dfs(int u,int fa)
{
f[u]=inf;g[u]=0;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa)continue;
dfs(v,u);
f[u]=min(f[u],f[v]+1);
g[u]=max(g[u],g[v]+1);
}
if(g[u]==k){ans++;f[u]=0;g[u]=-1;return;}
if(f[u]+g[u]<=k)g[u]=-1;
}
```
## [P4409 [ZJOI2006] 皇帝的烦恼](https://www.luogu.com.cn/problem/P4409)
有一种 $O(n\log n)$ 的 二分 + dp 的做法，这里不讲。讲一个非常妙的贪心做法。
先给出答案 $Ans=\max(a_i+a_{i-1},\lceil\dfrac{\sum a_i}{\lfloor\frac{n}{2}\rfloor}\rceil)$。下面简单证明一下。
显然有 $\forall\, i$，$Ans\ge a_i+a_{i-1}$，而我们发现在 $n$ 为偶数的时候， $Ans$ 取到 $\max(a_i+a_{i-1})$ 的时候是合法的（奇数位置和偶数位置各取一类，不会发生矛盾）。如果 $n$ 是奇数，这种方法就不太可行了（不能直接取等），因为有可能 $1$ 与 $n$ 发生矛盾。从另一个角度考虑问题，发现每一个勋章最多只能发给 $\lfloor\dfrac{n}{2}\rfloor$ 个人，所以至少需要 $\lceil\dfrac{\sum a_i}{\lfloor\frac{n}{2}\rfloor}\rceil$ 个勋章。最后就是两个取个 $\max$ 即可。
这题还有一个[多倍经验](https://www.luogu.com.cn/problem/UVA1335)，不过要注意开 long long，还有是多测。
## [[ARC136D] Without Carry](https://www.luogu.com.cn/problem/AT_arc136_d)
分析这道题，实际上是一个六维偏序，但是每一维的大小都不超过 $10$。我们知道，最朴素的偏序题可以使用前缀和去做，那么其实这道题就是使用高维前缀和去完成。
回想起二维前缀和的做法，我们一般都是用容斥的写法：`f[i][j]+=f[i][j-1]+f[i-1][j]-f[i-1][j-1]`。但是如果更高维，那岂不是要把式子写的很复杂？其实不然。我们可以这样先将第一维做完，然后再做第二维：
```cpp
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]+=f[i-1][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]+=f[i][j-1];
```
对于更高维前缀和也同理。但是，这里我们还可以用类似状压的思路把六个维的状态压到一个，然后对这个数进行前缀和。~~高维前缀和其实就是 SOS dp。~~
所以这道题就做完了。
```cpp
for(int base=1;base<A;base*=10)
for(int i=base;i<A;i++)
if(i/base%10)t[i]+=t[i-base];//第 i 维不是 0
```
## [CF1628D2 Game on Sum (Hard Version) ](https://www.luogu.com.cn/problem/CF1628D2)
首先考虑 Easy Version。发现 $k$ 是可以提出来的，所以可以设区间为 $[0,1]$，然后再在最后乘上 $k$。从 Alice 的角度思考，设 $f_{i,j}$ 表示玩了 $i$ 轮，然后使用了 $j$ 次 add 的最小值，那么有 $f_{i,j}=\min(f_{i-1,j-1}+t,f_{i-1,j}-t)$，其中 $t$ 是 Bob 给定的数。从 Bob 的角度思考，要使得 $f_{i,j}$ 尽可能大，那么当给定的 $t=\dfrac{f_{i-1,j}-f_{i-1,j-1}}{2}$ 的时候 $f_{i,j}$ 取得最大为 $\dfrac{f_{i-1,j-1}+f_{i-1,j}}{2}$。所以即可得到
$$f_{i,j}=\begin{cases}0 & (j=0)\\i & (j=i) \\ \dfrac{f_{i-1,j-1}+f_{i-1,j}}{2} & \text{otherwise}\end{cases}$$
时间复杂度为 $O(n^2)$。
考虑如何优化这玩意，发现一切的根源都在于类似 $f_{i,i}$ 的贡献，那么考虑 $f_{i,i}$ 最后对答案有多少贡献。正推可以发现，$(i,j)\to (i+1,j+1)$ 或 $(i,i)\to (i+1,j)$，概率都为 $\dfrac{1}{2}$，感觉有点像组合数？所以就是在 $n-i+1$ 个（$i+1\to n$）中选择 $m-i$ 个（$i\to m$），即贡献次数应该为 $\dfrac{\binom{n-i-1}{m-i}}{2^{n-i}}$。注意这里从 $(i+1,i)\to (n,m)$，而非 $(i,i)\to (n,m)$ 是因为 dp 的转移方程是在 $j<i$ 的情况开始转移的。注意特判 $n=m$ 的情况。
然后就可以 $O(n)$ 做完这玩意了。
```cpp
void solve()
{
n=read();m=read();k=read();ans=0;
if(n==m)return (void)printf("%lld\n",n*k%mod);
for(ll i=1;i<=m;i++)ans=(ans+i*C(n-i-1,m-i)%mod*pw[n-i]%mod)%mod;
printf("%lld\n",ans*k%mod);
}
```
## [[ABC321G] Electric Circuit](https://www.luogu.com.cn/problem/AT_abc321_g)
最难の题。不会图论导致的。
发现 $P$ 实际上的作用相当于对 $b$ 进行重拍，下面默认 $b$ 已经重排。
首先发现根据期望的线性性质，将答案转化成总数量/方案数。设 $f_S$ 表示集合 $S$ 为独立的方案数（即集合 $S$ 中的点不与其他的点有连边），那么必然需要满足集合 $S$ 中所有的 $a_i$ 都能匹配到一个 $b_i$，所以集合 $S$ 中的 $a,b$ 的数量 $cnt$ 需要相等，则答案为 $\displaystyle\prod_{i=1}^{cnt}i$，即 $cnt\,!$。
接下来设 $g_S$ 表示集合 $S$ 恰好形成一个连通块的方案数，这里使用容斥。具体而言，即枚举一个子集 $u$，减去 $u$ 作为一个独立的连通块的方案，即 $g_S=f_S-\displaystyle\sum_{u\subseteq S}g_u\times f_{S\oplus u}$。这里需要注意的是，为了避免多次枚举同种方案中的不同连通块（这样会导致重复计算），那么我们钦定，枚举的 $u$ 必须满足与 $S$ 的最小元素相同。最后设 $ans_S$ 表示连通块个数，同理枚举一个子集 $u$，那么有 $ans_S=\displaystyle\sum_{u\subseteq S}(ans_{S\oplus u}\times g_u+f_{S\oplus u}\times g_u)$，对于上面的这个规定同理。时间复杂度为枚举 subsubset 的 $O(3^n)$。
```cpp
for(int sta=0;sta<(1<<n);sta++)
{
int a=0,b=0;
for(int i=1;i<=n;i++)if((sta>>i-1)&1)a+=bucA[i],b+=bucB[i];
if(a==b)f[sta]=fac[a];
}
for(int sta=0;sta<(1<<n);sta++)
{
g[sta]=f[sta];int p=0;
for(int i=0;i<n;i++)if((sta>>i)&1){p=i;break;}
for(int u=(sta-1);u;u=(u-1)&sta)
if((u>>p)&1)g[sta]=(g[sta]-g[u]*f[sta^u])%mod;
g[sta]=(g[sta]+mod)%mod;
}
f[0]=1;
for(int sta=1;sta<(1<<n);sta++)
{
int p=0;
for(int i=0;i<n;i++)if((sta>>i)&1){p=i;break;}
for(int u=sta;u;u=(u-1)&sta)
if((u>>p)&1)ans[sta]=(ans[sta]+(ans[sta^u]+f[sta^u])*g[u])%mod;
}
```