$f(i,j)$: 安排前 $i$ 个工匠粉刷前 $j$ 块木板(可以有空着不刷的),工匠们能获得的最大报酬;

(1)第 $i$ 个工匠可以什么也不刷,此时：$f(i,j) = f(i-1,j)$;

(2)第 $j$ 块木板可以 空着 不刷,此时：$f(i,j) = f(i,j-1)$;

(3)第 $i$ 个工匠粉刷 $[k+1,j]$ 的木板，总数不超过$L_i$且必须包含$S_i$，

故：$k+1<=S_i<=j  即  k<=S_i-1;  j-k<=L_i  即  k>=j-L_i$

$f(i,j)=max\{ f(i-1,k) + P_i*(j-k) \}  (j-L_i<=k<=S_i-1, j>=S_i)$

优化：（细节请参考《算法竞赛进阶指南》 P315）

考虑内层循环$j$以及决策$k$时,可以把外层$i$看作定值,状态转移方程可改为：

$f(i,j)=P_i*j + max\{ f(i-1,k)-P_i*k \} (j-L_i<=k<=S_i-1, j>=S_i)$

当$j$增大时,决策 $k$ 的取值范围上界$S_i-1$不变，下界$j-L_i$变大，按与“最大子序列和”一题类似的想法，我们比较任意$2$个决策$k_1$和$k_2$，不妨假设$k_1<k_2<=S_i-1$：

因为$k_2>k_1$，随着j增大，$k_1$会比$k_2$更早从范围$[j-L_i,S_i-1]$中被排除，如果还满足:

$f(i-1,k_1)-P_i*k_1<=f(i-1,k_2)-P_i*k_2$,那么就意味着$k_2$比$k_1$更优且存活期更长。

这种情况下,$k_1$就是无用决策，从候选集排除即可。

综上所述，可以维护一个决策点$k$单调递增，数值$f(i-1,k)-P_i*k$单调递减的队列。

只有队列中的决策才有可能在某一时刻成为最优决策。

该单调队列支持如下操作：

1、$j$变大时，检查队头，把小于$j-L_i$的决策出队；

2、需要查询最优决策时，队头即所求；

3、新决策需要加入候选集时，在队尾检查$f(i-1,k)-P_i*k$的单调性，把无用决策出队，最后新决策入队。

具体操作：

内循环开始时($j=S_i$)，建立空队列，把$[max(S_i-L_i,0) , S_i-1]$中的决策加入候选集(操作$3$).对于每个$j=S_i$~$N$,

检查决策合法性(操作$1$),然后取队头为最优决策(操作$2$)进行状态转移。

每个决策最多入队、出队$1$次，故转移时间复杂度均摊$O(1)$,整体时间复杂度$O(NM)$

#include<iostream>

#include<algorithm>

using namespace std;

//协助计算马所能到达点

int fx[9]={0,-2,-1,1,2,2,1,-1,-2},fy[9]={0,1,2,2,1,-1,-2,-2,-1};

int ax,ay,mx,my;

long long ans;

long long f[30][30];

bool v[30][30];

int main()

{   freopen("pj024.in","r",stdin);

freopen("pj024.out","w",stdout);

   cin>>ax>>ay>>mx>>my;

   ax++;ay++;mx++;my++;

   //设置原点的路径数为1

   f[1][1]=1;

   //标记马所能走到的点

   v[mx][my]=1;

   for(int i=1;i<=8;i++)

   v[mx+fx[i]][my+fy[i]]=1;

   for(int i=1;i<=ax;i++)

       for(int j=1;j<=ay;j++)

       {

        //如果是马能走到的点，则跳过此次循环

           if(v[i][j])continue;

           //如果不是，则将能到达该点的路径数赋值为能到达它左边那点的路径数和能到达它上面那点的路径数之和（典型dp思想）

           f[i][j]=max(f[i][j],f[i-1][j]+f[i][j-1]);

       }

   //最终输出能到达B点的路径数

   cout<<f[ax][ay];

   cin>>ax;

   return 0;

}

对于一个「可调整的」 $n\times n$ 的 $01$ 矩阵，考虑在每一行与每一列的两个点间连一条边。

那么我们将得到一个 $2n$ 个点，$2n$ 条边的无向图，图中的每个连通块都是一个边数为偶数的简单环

https://blog.csdn.net/yanshannan/article/details/77453049 给出了一个图示。

可以发现，对于一个连通块，交换任意两行或两列之后，这些点仍然保持联通。

因此，每个连通块的大小确定了一个「可调整的」矩阵的等价类。

现在相当于把 $2n$ 个点拆分成若干连通块，求方案数。可以发现这里连通块的大小必须 $\ge 4$。

显然这等价于把 $n$ 无序地拆分成若干个 $\ge 2$ 的数。

考虑 DP，设 $f(i,j)$ 表示将 $i$ 无序地拆分成 $j$ 个 $\ge 2$ 正整数的方案数（其中 $i\ge 2j$），则有：

$$f(i,j)=f(i-2,j-1)+f(i-j,j)$$

其含义为，若拆分出的最小数为 $2$，那么相当于将除去 $2$ 后剩下的 $i-2$ 分成 $j-1$ 份；否则我们把拆出的每个数都减一，这部分的方案数就与 $f(i-j,j)$ 一一对应。

初值为 $f(0,0)=1$，答案为 $\sum_{2j\le n} f(n,j)$。

于是就做完了，时间复杂度 $O(n^2)$。

#include<bits/stdc++.h>//万能头文件

using namespace std;

int main(){

freopen("aplusb.in","r",stdin);//输入文件

freopen("aplusb.out","w",stdout);//输出文件

int a,b,c;//定义变量

cin>>a>>b;//输入

c=a+b;

cout<<c;//输出

fclose(stdin);

fclose(stdout);//关闭文件

return 0;//养成好习惯

}

（测试题解）

(注：此文设题中输入的图为 $G_1$，对应的完全图为 $G_2$，对应的补图为 $G_3$)

首先不难想到暴力思路：直接将 $G_2$ 建出来，跑一遍 MST 即可。

然而这样时间显然无法承受。

但是这道题显然有别的思路，考虑从特殊的边长：$0$ 和 $1$ 入手。

题中所给的边长为 $1$ 的边视为断边，建出 $G_3$，不难发现，答案就是补图的连通块数量减 $1$。

我们只需要算出连通块的数量即可，可以用并查集处理。

然而边数仍然很多，直接暴力求连通块很容易 TLE/MLE。

这时这个题目巧妙的地方就来了：我们可以将求解拆成两块，再合并答案。

首先发现，在原图 $G_1$ 中，设点 $i$ 的度数为 $deg_i$，不难发现$\sum\limits_{i=1}^n deg_i =2m$

那么根据抽屉原理，其中度数最小的点度数不超过 $\frac{2m}{n}$ ，设该点为 $u$ .

则可以先将 $G_1$ 中与 $u$ 没有连边的点和 $u$ 暴力合并，和 $u$ 有连边的点存储下来，暴力合并。

其中暴力合并的复杂度为 $O(N)$，则整体的时间复杂度为 $O(N+N\times \frac{2m}{N})=O(N+M)$.