动态规划100题 11~20 题
FjswYuzu
·
·
个人记录
## 11.「CF1101D」GCD Counting（思维树形 dp）
$\ \ \ \ \ \ \ $[luogu](https://www.luogu.com.cn/problem/CF1101D)
$\ \ \ \ \ \ \ $首先膜拜考场上面打点分治的巨佬 小ljs。
$\ \ \ \ \ \ \ $观察题面，似乎没有什么可以直接下手的地方。但是观察数据范围，$a_i$ 这么小，肯定有蹊跷嘛。
$\ \ \ \ \ \ \ $既然 $a_i \leq 2 \times 10^5$，所以 $a_i$ 的质因子应该极其之少，所以我们可以直接枚举质因子，大力 dp 就完了。
$\ \ \ \ \ \ \ $考场上不应该在这道题上面花那么多时间的。。。当然 $a_i$ 如果大了，那就过不了了。。
```cpp
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
//a_i 那么小，肯定有蹊跷
long long read()
{
long long x=0,f=1;
char c=getchar();
while(c<'0' || c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
return x*f;
}
vector<long long> prime[200005],appear[200005],G[200005];
long long n,a[200005],ans;
void dealWith(long long x,long long situ)
{
for(long long i=2;i*i<=x;++i)
{
if(x%i==0)
{
prime[situ].push_back(i);
appear[situ].push_back(1);
while(x%i==0) x/=i;
}
}
if(x>1) prime[situ].push_back(x),appear[situ].push_back(1);
}
void dfs(long long now,long long pre)
{
for(unsigned long long i=0;i<G[now].size();++i)
{
long long to=G[now][i];
if(to==pre) continue;
dfs(to,now);
for(unsigned long long j=0;j<prime[now].size();++j) for(unsigned long long k=0;k<prime[to].size();++k) if(prime[now][j]==prime[to][k]) ans=max(ans,appear[now][j]+appear[to][k]),appear[now][j]=max(appear[now][j],1+appear[to][k]);
}
if(a[now]>1) ans=max(ans,1ll);
}
int main(){
// freopen("count.in","r",stdin);
// freopen("count.out","w",stdout);
n=read();
bool flag=false;
for(long long i=1;i<=n;++i)
{
a[i]=read();
dealWith(a[i],i);
flag|=(a[i]>1);
}
if(!flag) return puts("0")&0;
for(long long i=1;i<n;++i)
{
long long u=read(),v=read();
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,0);
printf("%lld",ans);
while(1) return 0;
}
```
## 12.「JSOI2018」潜入行动（不简单的背包树形 dp）
$\ \ \ \ \ \ \ $[luogu](https://www.luogu.com.cn/problem/P4516)
$\ \ \ \ \ \ \ $初看题面：哦，这难道不是一道水题么？直接切嘛。
$\ \ \ \ \ \ \ $类似于分类讨论被自控，被爸爸控制，被儿子控制嘛。
$\ \ \ \ \ \ \ $再看题面，发现：如果在自己这里放上监控，是无法被控制的。于是我们的树形 dp 就宣告爆炸。
$\ \ \ \ \ \ \ $因为~~根据讨论~~理性分析之后，我们发现，其实被控制是根本一样的。只有自己放或者不放的区别。
$\ \ \ \ \ \ \ $考虑以上影响因素以及我们的经验，定义 $dp_{i,j,0\ or\ 1,0\ or\ 1}$ 表示以 $i$ 为根的子树用 $j$ 个监控器，（根可以不被监听，但是其它节点必须被监听）当前节点放不放监控器，根是否被监听，可以得到一个很长的 dp 方程，太长懒得打，就放在代码里面吧。
$\ \ \ \ \ \ \ $但是这样就完了吗？这道题的难点就在于，我们这样的时间复杂度是 $O(nk^2)$ 的！！那么放上朴素代码。
```cpp
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
//1
#define MOD 1000000007ll
using namespace std;
typedef long long LL;
/*
dp[i][j][0/1][0/1]:
以i为根，放j个监听器，根放了没有，被监听没有。
*/
vector<int> G[100005];
long long read()
{
long long x=0,f=1;
char c=getchar();
while(c<'0' || c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
return x*f;
}//2
int dp[100005][105][2][2],tmpdp[105][2][2],sizen[100005],n,k;
void DP(long long now,long long pre)
{
dp[now][0][0][0]=dp[now][1][1][0]=sizen[now]=1;
for(unsigned int i=0;i<G[now].size();++i)
{
int to=G[now][i];
if(to==pre) continue;
DP(to,now);
memset(tmpdp,0,sizeof tmpdp);
for(int j=0;j<=k;++j)
{
for(int l=0;l<=k-j;++l)//3
{
tmpdp[j+l][0][0]+=(
(LL)dp[now][j][0][0]*dp[to][l][0][1])%MOD,
tmpdp[j+l][0][0]%=MOD;
tmpdp[j+l][0][1]+=(((
(LL)dp[now][j][0][1]*dp[to][l][0][1])%MOD+
(LL)dp[now][j][0][1]*dp[to][l][1][1])+
(LL)dp[now][j][0][0]*dp[to][l][1][1])%MOD,
tmpdp[j+l][0][1]%=MOD;
tmpdp[j+l][1][0]+=((
(LL)dp[now][j][1][0]*dp[to][l][0][1])+
(LL)dp[now][j][1][0]*dp[to][l][0][0])%MOD,
tmpdp[j+l][1][0]%=MOD;
tmpdp[j+l][1][1]+=((((((
(LL)dp[now][j][1][1]*dp[to][l][0][0])%MOD+
(LL)dp[now][j][1][1]*dp[to][l][0][1])+
(LL)dp[now][j][1][1]*dp[to][l][1][0])%MOD+
(LL)dp[now][j][1][1]*dp[to][l][1][1])+
(LL)dp[now][j][1][0]*dp[to][l][1][0])+
(LL)dp[now][j][1][0]*dp[to][l][1][1])%MOD,
tmpdp[j+l][1][1]%=MOD;//dp方程
}
}
sizen[now]+=sizen[to];
memcpy(dp[now],tmpdp,sizeof tmpdp);
}
}
int main(){
// freopen("sneak.in","r",stdin);
// freopen("sneak.out","w",stdout);
n=read(),k=read();
for(int i=1;i<n;++i)
{
int u=read(),v=read();
G[u].push_back(v);
G[v].push_back(u);
}
DP(1,0);
printf("%lld",(dp[1][k][0][1]+dp[1][k][1][1])%MOD);
while(1) return 0;
}
```
$\ \ \ \ \ \ \ $于是我们只能考虑优化。首先来试一下优化常数吧。
$\ \ \ \ \ \ \ $优化 1（对应注释1）：你的八聚氧。
$\ \ \ \ \ \ \ $优化 2（对应注释2）：你的 `fread()`。
$\ \ \ \ \ \ \ $优化 3（对应注释3）：放不了这么多放什么放，把 `j<=k` 改成 `min(k,sizen[now])`，`l<=k-j` 改成 `min(k-j,sizen[to])`。
$\ \ \ \ \ \ \ $交一发，为什么 A 了？？
$\ \ \ \ \ \ \ $删去优化 1 和 2，发现其实 1 和 2 并没有起很大作用，删掉 3 就只有 30 分了。这是为什么呢？
$\ \ \ \ \ \ \ $首先分析一下复杂度，这个优化看似是一个常数优化，但是实际上起到了至关重要的作用。
$\ \ \ \ \ \ \ $考虑证明，思来想去也不过三种情况：
1. 一个节点有两个儿子形成的子树大小大于 $k$：实际上合并次数就不会超过 $O(\frac{n}{k})$ 了。这样之后就会变成 $O(k)$。实际上这应该是最快的一种情况。
2. 一个节点有一个儿子形成的子树大小小于 $k$，合并了就成了大于 $k$ 了：因为子树的所有节点都经过一次背包合并，实际上均摊之后也只有 $O(k)$ 了。
3. otherwise：显然这个东西是不足 $O(k)$ 的。每次加入一个点，不足 $k$ 个节点，那么对于某一个特定的点，它的贡献实际上是每次加入的子树大小，还没有 $O(k)$ 了。
$\ \ \ \ \ \ \ $综上所述：我们的时间复杂度为 $O(nk)$。
```cpp
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#define MOD 1000000007ll
using namespace std;
typedef long long LL;
/*
dp[i][j][0/1][0/1]:
以i为根，放j个监听器，根放了没有，被监听没有。
*/
vector<int> G[100005];
long long read()
{
long long x=0,f=1;
char c=getchar();
while(c<'0' || c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
return x*f;
}
int dp[100005][105][2][2],tmpdp[105][2][2],sizen[100005],n,k;
void DP(long long now,long long pre)
{
dp[now][0][0][0]=dp[now][1][1][0]=sizen[now]=1;
for(unsigned int i=0;i<G[now].size();++i)
{
int to=G[now][i];
if(to==pre) continue;
DP(to,now);
memset(tmpdp,0,sizeof tmpdp);
for(int j=0;j<=min(k,sizen[now]);++j)
{
for(int l=0;l<=min(k-j,sizen[to]);++l)
{
tmpdp[j+l][0][0]+=(
(LL)dp[now][j][0][0]*dp[to][l][0][1])%MOD,
tmpdp[j+l][0][0]%=MOD;
tmpdp[j+l][0][1]+=(((
(LL)dp[now][j][0][1]*dp[to][l][0][1])%MOD+
(LL)dp[now][j][0][1]*dp[to][l][1][1])+
(LL)dp[now][j][0][0]*dp[to][l][1][1])%MOD,
tmpdp[j+l][0][1]%=MOD;
tmpdp[j+l][1][0]+=((
(LL)dp[now][j][1][0]*dp[to][l][0][1])+
(LL)dp[now][j][1][0]*dp[to][l][0][0])%MOD,
tmpdp[j+l][1][0]%=MOD;
tmpdp[j+l][1][1]+=((((((
(LL)dp[now][j][1][1]*dp[to][l][0][0])%MOD+
(LL)dp[now][j][1][1]*dp[to][l][0][1])+
(LL)dp[now][j][1][1]*dp[to][l][1][0])%MOD+
(LL)dp[now][j][1][1]*dp[to][l][1][1])+
(LL)dp[now][j][1][0]*dp[to][l][1][0])+
(LL)dp[now][j][1][0]*dp[to][l][1][1])%MOD,
tmpdp[j+l][1][1]%=MOD;
}
}
sizen[now]+=sizen[to];
memcpy(dp[now],tmpdp,sizeof tmpdp);
}
}
int main(){
// freopen("sneak.in","r",stdin);
// freopen("sneak.out","w",stdout);
n=read(),k=read();
for(int i=1;i<n;++i)
{
int u=read(),v=read();
G[u].push_back(v);
G[v].push_back(u);
}
DP(1,0);
printf("%lld",(dp[1][k][0][1]+dp[1][k][1][1])%MOD);
while(1) return 0;
}
```
## 13.「CF1114D」Flood Fill（套路区间 dp）
$\ \ \ \ \ \ \ $[luogu](https://www.luogu.com.cn/problem/CF1114D)
$\ \ \ \ \ \ \ $实际上这是个模板。考虑枚举长度和长度区间，区间枚举划分点，这实际上是 $O(n^3)$ 的。只能优化区间划分点。每次加入的话，其实是不需要枚举划分点的。把序列 `unique` 掉，每次加入就不会有相同的影响了。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,dp[5005][5005],a[5005],len;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
len=unique(a+1,a+1+n)-a-1;
for(int i=1;i<=len;++i)
{
for(int l=1,r=i+1;r<=len;++l,++r)
{
if(a[l]==a[r]) dp[l][r]=dp[l+1][r-1]+1;
else dp[l][r]=min(dp[l+1][r],dp[l][r-1])+1;
}
}
printf("%d",dp[1][len]);
return 0;
}
```
## 14.「CF149D」Coloring Brackets（限制性区间 dp）
$\ \ \ \ \ \ \ $[luogu](https://www.luogu.com.cn/problem/CF149D)
$\ \ \ \ \ \ \ $其实也是裸题，只不过加上了一些预处理和颜色限制。我们首先考虑计算括号对应，很容易打出这样的代码。
```cpp
for(long long i=1;i<=n;++i)
{
if(bracket[i]=='(') S.push(i);
else dy[S.top()]=i,S.pop();
}
```
$\ \ \ \ \ \ \ $加上颜色限制，定义 $dp_{i,j,0 \ or \ 1 or \ 2,0 \ or \ 1 or \ 2}$ 为区间 $[i,j]$，$i$ 不染/染成红色/染成蓝色，$j$ 同理的方案数，递归长序列，dp 合并小序列：
- 如果 $l+1=r$ ，因为这是一个合法的括号序列，包含下面的操作话这一定是一对括号；
- 如果 $dy_l=r$，递归处理 $l+1,r-1$，合并组成 dp；
- 其他情况是最麻烦的，这是两个或以上的括号序列组成的，分别划分，依次 dp，合并即可。
$\ \ \ \ \ \ \ $详见代码。
```cpp
#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cstring>
#include<stack>
#define MOD 1000000007ll
using namespace std;
stack<long long> S;
long long dp[705][705][3][3],dy[705],n;
char bracket[705];
/*
dp[l][r][0/1/2][0/1/2];
[l,r] l=0/1/2 r=0/1/2
还是写记忆化好理解。xd
*/
void dfs(long long l,long long r)
{
if(l+1==r)
{
dp[l][r][0][1]=dp[l][r][0][2]=dp[l][r][1][0]=dp[l][r][2][0]=1;
return ;
}
if(dy[l]==r)
{
dfs(l+1,r-1);
for(long long i=0;i<=2;++i)
{
for(long long j=0;j<=2;++j)
{
if(i!=1) dp[l][r][1][0]+=dp[l+1][r-1][i][j],dp[l][r][1][0]%=MOD;
if(i!=2) dp[l][r][2][0]+=dp[l+1][r-1][i][j],dp[l][r][2][0]%=MOD;
if(j!=1) dp[l][r][0][1]+=dp[l+1][r-1][i][j],dp[l][r][0][1]%=MOD;
if(j!=2) dp[l][r][0][2]+=dp[l+1][r-1][i][j],dp[l][r][0][2]%=MOD;
}
}
}
else
{
dfs(l,dy[l]);
dfs(dy[l]+1,r);
for(long long i=0;i<=2;++i) for(long long j=0;j<=2;++j) for(long long k=0;k<=2;++k) for(long long m=0;m<=2;++m) if(!(j && j==k)) dp[l][r][i][m]+=dp[l][dy[l]][i][j]*dp[dy[l]+1][r][k][m]%MOD,dp[l][r][i][m]%=MOD;
}
}
int main(){
// freopen("coloring.in","r",stdin);
// freopen("coloring.out","w",stdout);
scanf("%s",bracket+1);
n=strlen(bracket+1);
for(long long i=1;i<=n;++i)
{
if(bracket[i]=='(') S.push(i);
else dy[S.top()]=i,S.pop();
}
dfs(1,n);
long long ans=0;
for(long long i=0;i<=2;++i) for(long long j=0;j<=2;++j) ans+=dp[1][n][i][j],ans%=MOD;
printf("%lld",ans);
return 0;
}
```
## 15.「CQOI2009」叶子的染色（猜结论+树形 dp）
$\ \ \ \ \ \ \ $[luogu](https://www.luogu.com.cn/problem/P3155)
$\ \ \ \ \ \ \ $真的没想到 T3 是最简单的。。。
$\ \ \ \ \ \ \ $首先猜个结论：怎么选根答案都是一样的。（毕竟这是猜结论，我也不知道为什么）。
$\ \ \ \ \ \ \ $然后再一个结论：我们把叶子染色，实际上就是把根染色。因为叶子染色只跟上面的颜色有关。
$\ \ \ \ \ \ \ $然后就完了？？定义 $dp_{i,0 \ or \ 1}$ 为 $i$ 为根，$i$ 染成黑色还是白色。则有 dp 方程：
$$\begin{cases}
dp_{now,0}=\sum_{\texttt{now的孩子们to}}\min \{dp_{to,1},dp_{to,0}-1\} \\\\
dp_{now,1}=\sum_{\texttt{now的孩子们to}}\min \{dp_{to,0},dp_{to,1}-1\}
\end{cases}$$
$\ \ \ \ \ \ \ $然后真的就完了。注意排斥掉和叶子颜色不同的方案。
```cpp
#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
vector<int> G[100005];
bool color[100005];
int dp[100005][2],m,n;
/*
dp[root][0/1]:root 为根 染成什么 最少多少个。
*/
void dfs(int now,int pre)
{
if(now<=n)
{
dp[now][color[now]]=1;
dp[now][!color[now]]=2147483647;
return ;
}
dp[now][1]=dp[now][0]=1;
for(unsigned int i=0;i<G[now].size();++i)
{
int to=G[now][i];
if(to==pre) continue;
dfs(to,now);
dp[now][0]+=min(dp[to][1],dp[to][0]-1);
dp[now][1]+=min(dp[to][1]-1,dp[to][0]);
}
}
int main(){
freopen("leave.in","r",stdin);
freopen("leave.out","w",stdout);
scanf("%d %d",&m,&n);
for(int i=1,tmp;i<=n;++i) scanf("%d",&tmp),color[i]=bool(tmp);
for(int i=1;i<m;++i)
{
int u,v;
scanf("%d %d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(n+1,-1);
printf("%d",min(dp[n+1][0],dp[n+1][1]));
return 0;
}
```
## 16.「HAOI2016」字符合并（区间 dp x 状压 dp）
$\ \ \ \ \ \ \ $[luogu](https://www.luogu.com.cn/problem/P3736)
$\ \ \ \ \ \ \ $根据经验，$k$ 很小，并且只有 01 串，很容易想到状压 dp。
$\ \ \ \ \ \ \ $因为分数非负，考虑把能合的全部都合起来。我们考虑合并完成后展开，各个区间一定是不相交的。考虑用上区间 dp。
$\ \ \ \ \ \ \ $区间 dp 套路，枚举中间端点。合并成一位 0 或 1 一定会弄掉 $k$ 个字符变成 1 个（因为其中区间不相交），所以直接 `ptt+=k-1` 就好。
$\ \ \ \ \ \ \ $然后特殊情况是区间长度刚好是 $k$。那么直接合并，用两个临时变量储存。（因为修改之后能够修改其他的值，不好操作）。
$\ \ \ \ \ \ \ $最后说一下状态定义：定义 $dp_{i,j,S}$ 为合并 $[i,j]$ 区间，状态为 $S$。有 dp 方程：
$$\begin{cases}
dp_{i,j,now \times 2}=\max \{ dp_{i,ptt-1,now} + dp_{ptt,j,0}\}(dp_{ptt,j,0}!=-inf) \\\\ dp_{i,j,now \times 2+1}=\max \{ dp_{i,ptt-1,now} + dp_{ptt,j,1}\}(dp_{ptt,j,1}!=-inf)
\end{cases}$$
$\ \ \ \ \ \ \ $最后注意下枚举顺序，考虑用到 $dp_{i,ptt-1}$ 和 $dp_{ptt,j}$，枚举区间一定要倒序枚举。
$\ \ \ \ \ \ \ $答案为 $\max \{ dp_{1,n}\}
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<set>
#include<map>
#define lc(x) x<<1ll
#define rc(x) x<<1ll|1ll
using namespace std;
char t[3005];
int n,m;
long long NegaInf,a[3005],cnt[2600],val[2600],dp[305][305][305];
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
for(int i=0;i<=(1<<m)-1;++i) scanf("%lld %lld",&cnt[i],&val[i]);
memset(dp,128,sizeof dp);
for(int i=1;i<=n;++i) dp[i][i][a[i]]=0;
NegaInf=dp[0][0][0];
for(int dis=2;dis<=n;++dis)
{
for(int i=1,j=dis;j<=n;++i,++j)
{
long long lena=(j-i)%(m-1);
lena=!lena?m-1:lena;
for(int ptt=j;ptt>=i+1;ptt-=m-1)
{
for(int k=0;k<=(1<<lena)-1;++k)
{
if(dp[i][ptt-1][k]==NegaInf) continue;
if(dp[ptt][j][0]!=NegaInf) dp[i][j][lc(k)]=max(dp[i][j][lc(k)],dp[i][ptt-1][k]+dp[ptt][j][0]);
if(dp[ptt][j][1]!=NegaInf) dp[i][j][rc(k)]=max(dp[i][j][rc(k)],dp[i][ptt-1][k]+dp[ptt][j][1]);
}
}
if(lena==m-1)
{
long long rear0=NegaInf,rear1=NegaInf;
for(int k=0;k<=(1<<m)-1;++k)
{
if(dp[i][j][k]!=NegaInf)
{
if(cnt[k]) rear1=max(rear1,dp[i][j][k]+val[k]);
else rear0=max(rear0,dp[i][j][k]+val[k]);
}
}
dp[i][j][0]=rear0,dp[i][j][1]=rear1;
}
}
}
long long ans=NegaInf;
for(int i=0;i<=(1<<m)-1;++i) ans=max(ans,dp[1][n][i]);
printf("%lld",ans);
return 0;
}
17.「GXOI/GZOI2019」宝牌一大堆（我也不知道是什么 dp）
$\ \ \ \ \ \ \ $作为一个玩雀魂的想做一下麻将题，发现 ZJOI 的麻将题过于毒瘤，这个反而比较简单。
$\ \ \ \ \ \ \ $考虑到只有刻子/顺子/杠子/雀头，面子与雀头只跟当前牌，下一张牌，下下张牌有关系，其他需要注意的有组成了多少个面子，有没有雀头。考虑到将这五个东西联合当前牌是什么塞进 dp 中。但是我们很快发现在这个模式下杠了牌就是[杠精](https://zh.moegirl.org/%E6%97%A5%E6%9C%AC%E9%BA%BB%E5%B0%86:%E6%9D%A0%E7%B2%BE)，原因是 $C_4^3=4C_4^4$。即使这张牌是 dora 也无济于事，没有用。~~（杠杠杠，杠出新天地，杠出宝牌一大堆）~~
$\ \ \ \ \ \ \ $现在考虑到这六维的信息。定义 $dp_{i,,j1 \ or \ 0,k,l,o}$ 为在第 $i$ 张牌（共有 34 张牌），组成的牌中有没有雀头，组成了 $j$ 个面子，$i$ 张牌用了 $k$ 张，第 $i+1$ 张牌用了 $l$ 张，$i+2$ 用了 $o$ 张，分有无雀头两边 dp，分情况讨论新组成顺子，新组成刻子，新组成雀头就OK了。
$\ \ \ \ \ \ \ $定义 $dp_{i,j,0 \ or \ 1 ,k,l,o}$ 为选到 $i$ 张牌，组成 $j$ 刻子，有无雀头，$i$ 张牌用了 $k$ 张，$i+1$ 用了 $l$ 张，$i+2$ 用了 $o$ 张。对有无雀头分别 dp，考虑新增雀头/刻子/顺子讨论即可。
$\ \ \ \ \ \ \ $超时了，考虑优化：
- $l \leq 2,o \leq 2$。这是因为当 $l>2$ 时，它是一个刻子，更别说 $l>2,o>2$ 了，这直接是一个三连刻好吗？（你听说过三连刻没有.jpg，古役，两番？）；（优化 1）
- 组合数打表计算，不要直接计算；（优化 2）
- 如果当前 dp 值为 0，直接 `continue`，这是因为你之前组成的牌胡不了。。（优化 3）
$\ \ \ \ \ \ \ $七对子贪心选择贡献最大的七个对子，国士无双（三大民工役满之一，剩下为大三元和四暗刻）枚举哪一张用两次，$O(169)$ 枚举就 OK。
$\ \ \ \ \ \ \ $看不懂就领略一下精神就好了。。。
```cpp
#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cstring>
#define mahjongMaxn 35
using namespace std;
const int initC[7][7]=
{
{1,0,0,0,0},
{1,1,0,0,0},
{1,2,1,0,0},
{1,3,3,1,0},
{1,4,6,4,1}
};//一定要做的事
void write(long long t)
{
if(t<0) putchar('-'),t=-t;
if(t>9) write(t/10);
putchar('0'+t%10);
}
const int Kin[]={0,1,9,10,18,19,27,28,29,30,31,32,33,34};//国士无双需要的牌，Kokushimusou in need
const bool shien[]={0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0};//能做顺子开头的牌
int rest[mahjongMaxn+5],isDora[mahjongMaxn+5];//剩下多少张以及是否是 dora
long long dp[mahjongMaxn+5][6][4][6][4][4];
int C(int x,int y){return initC[x][y];}//可以换成正常计算（优化 2）
int mahjong(char x)
{
switch (x)
{
case 'E': return 28;
case 'S': return 29;
case 'W': return 30;
case 'N': return 31;
case 'Z': return 32;
case 'B': return 33;
case 'F': return 34;
}
return 10086001;
}
int mahjong(char x,char y)
{
switch (y)
{
case 'm': return x-'0';
case 'p': return 9+x-'0';
case 's': return 18+x-'0';
}
return 10086001;
}//输入，返回麻将标号
long long Kokushimusou()
{
for(int i=1;i<=13;++i) if(!rest[Kin[i]]) return 0;
long long ans=0;
for(int i=1;i<=13;++i)
{
long long tmp=C(rest[Kin[i]],2)*isDora[Kin[i]]*isDora[Kin[i]]*13;
for(int j=1;j<=13;++j) if(i!=j) tmp*=isDora[Kin[j]]*rest[Kin[j]];
ans=max(ans,tmp);
}
return ans;
}//国士无双
long long Chitoicu()
{
long long ans=7;
priority_queue<long long> PQ;
for(int i=1;i<=mahjongMaxn-1;++i) PQ.push(isDora[i]*isDora[i]*C(rest[i],2));
if(PQ.size()<7) return 0;
for(int i=1;i<=7;++i) ans*=PQ.top(),PQ.pop();
return ans;
}//七对子
long long OthersDP(){
long long ans=0;
dp[1][0][0][0][0][0]=1;
for(int i=1;i<=mahjongMaxn-1;++i)
{
for(int j=0;j<=4;++j)
{
for(int k=0;k<=4;++k)
{
for(int l=0;l<=2;++l)
{
for(int o=0;o<=2;++o)//（优化 1）
{
long long kc1=dp[i][j][0][k][l][o],kc2=dp[i][j][1][k][l][o];
if(!kc1 && !kc2) continue;//（优化 3）
if(rest[i]-k>=2) dp[i][j][1][k+2][l][o]=max(dp[i][j][1][k+2][l][o],kc1/C(rest[i],k)*C(rest[i],k+2)*isDora[i]*isDora[i]);//新雀头
if(j<4)
{
if(rest[i]-k>=3)
dp[i][j+1][0][k+3][l][o]=
max(dp[i][j+1][0][k+3][l][o],
kc1/C(rest[i],k)*C(rest[i],k+3)*isDora[i]*isDora[i]*isDora[i]),
dp[i][j+1][1][k+3][l][o]=
max(dp[i][j+1][1][k+3][l][o],
kc2/C(rest[i],k)*C(rest[i],k+3)*isDora[i]*isDora[i]*isDora[i]);//新刻子
if(shien[i] && rest[i]>k && rest[i+1]>l && rest[i+2]>o && l!=2 && o!=2)
dp[i][j+1][0][k+1][l+1][o+1]=max(dp[i][j+1][0][k+1][l+1][o+1],
kc1
/C(rest[i],k)*C(rest[i],k+1)*isDora[i]
/C(rest[i+1],l)*C(rest[i+1],l+1)*isDora[i+1]
/C(rest[i+2],o)*C(rest[i+2],o+1)*isDora[i+2]),
dp[i][j+1][1][k+1][l+1][o+1]=max(dp[i][j+1][1][k+1][l+1][o+1],
kc2
/C(rest[i],k)*C(rest[i],k+1)*isDora[i]
/C(rest[i+1],l)*C(rest[i+1],l+1)*isDora[i+1]
/C(rest[i+2],o)*C(rest[i+2],o+1)*isDora[i+2]);//新顺子
}
dp[i+1][j][0][l][o][0]=max(dp[i+1][j][0][l][o][0],kc1);
dp[i+1][j][1][l][o][0]=max(dp[i+1][j][1][l][o][0],kc2);//自身状态继承下一状态
if(j==4) ans=max(ans,kc2);//四个刻子和一个雀头就以经胡牌，保存答案
}
}
}
}
}
return ans;
}
void Prepare()
{
fill(rest,rest+mahjongMaxn,4);
fill(isDora,isDora+mahjongMaxn,1);
memset(dp,0,sizeof dp);
}
void ReadMahjongRiver()
{
char s[2];
while(scanf("%s",s))
{
if(s[0]=='0') return ;
if(s[1]=='\0') --rest[mahjong(s[0])];
else --rest[mahjong(s[0],s[1])];
}
}
void ReadDora()
{
char s[2];
while(scanf("%s",s))
{
if(s[0]=='0') return ;
if(s[1]=='\0') isDora[mahjong(s[0])]=2;
else isDora[mahjong(s[0],s[1])]=2;
}
}//Input
int main(){
long long T;
scanf("%lld",&T);
while(T-->0)
{
Prepare();
ReadMahjongRiver();
ReadDora();
write(max({Chitoicu(),Kokushimusou(),OthersDP()}));//C++11标准
puts("");
}
return 0;
}
```
## 18.「UVA1452」Jump（约瑟夫问题变形）
$\ \ \ \ \ \ \ $[luogu](https://www.luogu.com.cn/problem/UVA1452)
$\ \ \ \ \ \ \ $注：以上皆为 0 开头，代表队伍中的 1，$n-1$ 代表第 $n$ 人。
$\ \ \ \ \ \ \ $这实际上是一个约瑟夫问题的一个变形。首先回到约瑟夫问题，它的实质是：将 $n$ 个人的子问题化成 $n-1$ 个，在同时建立一个映射关系，也就是我们的递推数组。我们要求最后一个人，就要倒退回去推出 $n$ 个人的情况。得到了最后一个人是谁，在倒推倒数第二人，倒数第三人即可。
$\ \ \ \ \ \ \ $所以我们定义 $dp_i$ 为 $i-1$ 个人出列后，接下来应该让谁出列（同时调整队列顺序与编号）。我们最后一个出列的人因为在队头，所以编号一定为 0。因此 $dp_1=0$。题目定义得出递推方程：
$$dp_{i-1}=dp_i-k(\mod i)$$
$\ \ \ \ \ \ \ $即：
$$dp_i=dp_{i-1}+k(\mod i)$$
$\ \ \ \ \ \ \ $考虑到我们要求倒数三个人，所以分别令 $dp_1=0,dp_1=1,dp_2=2$ 就可以分别求出倒数第一个，倒数第二个和第三个了。
$\ \ \ \ \ \ \ $这里就直接把数组滚了，代码会有点奇怪。因为 0 是开头，所以答案注意加 1。
$\ \ \ \ \ \ \ $滚了数组之后代码可能有点怪，可以自行理解一下。
```cpp
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int main(){
int T;
scanf("%d",&T);
while(T-->0)
{
int n,k;
scanf("%d %d",&n,&k);
int a=0,b=(k-1)%2,c=(k-1)%3;
for(int i=2;i<=n;++i) a+=k,a%=i;
for(int i=3;i<=n;++i) b+=k,b%=i;
for(int i=4;i<=n;++i) c+=k,c%=i;
printf("%d %d %d\n",c+1,b+1,a+1);
}
return 0;
}
```
## 19.「CF235B」Let's play OSU! 和 「BZOJ4318」OSU!（期望 dp）
$\ \ \ \ \ \ \ $[luogu1](https://www.luogu.com.cn/problem/CF235B) [luogu2](https://www.luogu.com.cn/problem/P1654)
$\ \ \ \ \ \ \ $因为前者是后者的简化版，所以放一起了，~~我多良心啊~~。
$\ \ \ \ \ \ \ $因为 $(x+1)^2=x^2+2x+1$，而 $E(x+y)=E(x)+E(y)$，我们设 $osu$ 为线性期望（类似于一次），$dp$ 表示答案。很容易得到：
$$osu_i=(osu_{i-1}+1) \times p_i$$
$$dp_i=dp_{i-1}+p_i \times (2 \times osu_{i-1} +1)$$
$\ \ \ \ \ \ \ $综上，答案为 $dp_n$。
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
double osu[100005],dp[100005];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
double cure;
scanf("%lf",&cure);
osu[i]=cure*(osu[i-1]+1);
dp[i]=dp[i-1]+cure*(2*osu[i-1]+1);
}
printf("%.10f",dp[n]);
return 0;
}
```
$\ \ \ \ \ \ \ $然后看到加强版。
$\ \ \ \ \ \ \ $因为 $(x+1)^3=x^3+3x^2+3x+1$。
$\ \ \ \ \ \ \ $考虑到 $E(x)$ 中的 $x$ 增加 1，答案就多了 $E(3x^2+3x+1)$。又去考虑 $(x+1)^2$，同理可得。线性的比较简单，不再概述。
$\ \ \ \ \ \ \ $返回到题目，用 $osu1$ 维护 $x$ 的期望，$osu2$ 维护 $x^2$ 的期望，$dp$ 维护答案，也就是 $x^3$ 的期望，有：
$$osu1_i=(osu1_{i-1}+1) \times p_i$$
$$osu2_i=(osu2_{i-1}+2 \times osu1_{i-1} + 1) \times p_i$$
$$dp_i=dp_{i-1}+(3 \times osu2_{i-1} + 3 \times osu1_{i-1}+1) \times p_i$$
$\ \ \ \ \ \ \ $综上，答案为 $dp_n$。
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
double osu1[100005],osu2[100005],dp[100005];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
double cure;
scanf("%lf",&cure);
osu1[i]=(osu1[i-1]+1)*cure;
osu2[i]=(osu2[i-1]+2*osu1[i-1]+1)*cure;
dp[i]=dp[i-1]+(3*osu2[i-1]+3*osu1[i-1]+1)*cure;
}
printf("%.1f",dp[n]);
return 0;
}
```
$\ \ \ \ \ \ \ $至于为什么变量名叫 `cure`，是因为玩 OSU 需要解药。
$\ \ \ \ \ \ \ $我怎么就管不住我这手呢？？？
## 20.「CF76F」Tourist（LIS 变形）
$\ \ \ \ \ \ \ $[luogu](https://www.luogu.com.cn/problem/CF76F)
$\ \ \ \ \ \ \ $不得不说是一道好题。
$\ \ \ \ \ \ \ $考虑到我们将每一个事件按时间排序之后，可以很容易的得到 dp 式。我们从一个点走到另外一个点，dp 值加 1 即可。
$\ \ \ \ \ \ \ $一个点走到另一个点的条件是：$|x_i-x_j| \leq |t_i-t_j| \times v$。从这里怎么下手？
$\ \ \ \ \ \ \ $首先说结论，$-x_i+t_i \times v \leq -x_i+t_j \times v \operatorname{and} x_i+t_i \times v \leq x_j+t_j \times v$ 和上面那个式子等价。
$\ \ \ \ \ \ \ $假设 $t_i \leq t_j$，当 $x_i \geq x_j$ 时，$x_i -x_j \leq (t_j -t_i) \times v$ ，否则 $x_j-x_i \leq (t_j-t_i)\times v$。
$\ \ \ \ \ \ \ $去掉前提。我们假设 $a_i=x_i + t_i \times v,b_i=x_i+t_j \times v$。如果一个点走到另一个点的话，必有 $a_i \leq a_j,b_i \leq b_j$。
$\ \ \ \ \ \ \ $这里没看懂可以在理解一下，是挺麻烦的。
$\ \ \ \ \ \ \ $现在我们得出 $a_i,b_i$ 单调。按 $a_i,b_i$ 排个序，求最长不下降子序列就行了。特殊的，对于第一个问题，我们只需要 $a_i,b_i \geq 0$ 的点就行了。
```cpp
#include<cstdio>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
#include<cstring>
using namespace std;
int x[100005],t[100005],n,v;
struct Point{//Map to an event.
int x,y;
bool operator < (Point q) const
{
if(x!=q.x) return x<q.x;
return y<q.y;
}
Point() {}
Point(int X,int Y){x=X,y=Y;}
}event[100005];
int main(){
cin>>n;
for(int i=1;i<=n;++i) cin>>x[i]>>t[i];
cin>>v;
int tot=0;
for(int i=1;i<=n;++i) if(v*t[i]+x[i]>=0 && v*t[i]-x[i]>=0) event[++tot]=Point(v*t[i]+x[i],v*t[i]-x[i]);
sort(event+1,event+1+tot);
multiset<int> S;
multiset<int>::iterator Sit;
for(int i=1;i<=tot;++i)
{
Sit=S.upper_bound(event[i].y);
if(Sit!=S.end()) S.erase(Sit);
S.insert(event[i].y);
}
cout<<S.size()<<' ';
S.clear();
for(int i=1;i<=n;++i) event[i]=Point(v*t[i]+x[i],v*t[i]-x[i]);
sort(event+1,event+1+n);
for(int i=1;i<=n;++i)
{
Sit=S.upper_bound(event[i].y);
if(Sit!=S.end()) S.erase(Sit);
S.insert(event[i].y);
}
cout<<S.size()<<endl;
return 0;
}
```