以前存在本地的东西，发上来方便找（x）

动态规划

模型

背包

01背包(f[i][j]=max(f[i-1][j],f[i-1][j-w_i]+v_i))

完全背包（每个物品次数不限），那就用(f[i][j]=max(f[i-1][j],f[i][j-w_i]+v_i))，滚动数组的时候对于体积直接从小到大枚举就好。

多重背包（第(i)种物品有(k_i)个），大暴力是(O(nmsum k_i))，二进制拆分(k_i=1+2+dots+2^t+(k_i-(1+2+dots,2^t)))，复杂度(O(nmsumlog k_i))

int x;scanf("%d",&x);
int c=1;
while(x>c){
    x-=c;
    w[++n]=W[i]*c;
    v[n]=V[i]*c
    c<<=1;
}
if(x)w[++n]=W[i]*x,v[n]=V[i]*x;

单调队列优化多重背包

暴力dp：(f[i][j]=max_{k=0}^{k_i}(f[i-1][j-k*w[i]]+k*v[i]))，这样对每一个(i)转移的代价是(O(msum k_i))的。接着我们注意到，对于(0leq j<w[i])，(f[i-1][j],f[i-1][j+w[i]],f[i-1][j+2w[i]],dots)这样一系列位置会对(f[i][j+kw[i]])造成影响，我们考虑枚举(j=0,dots,w[i]-1)，再去枚举(k)，用单调队列来优化求(f[i])的过程，这样总复杂度就是(O(nsum w_ifrac{W}{w_i})=O(nW))，其中(W)是背包的大小。

二维费用背包：和普通背包类似，多记录一维代价。

分组背包：组内的物品互相冲突不能同时选择，改成先枚举组，然后是体积，最后才是组内的所有物品：

for(int k=1;k<=K;k++)for(int j=V;j>=0;j--)for(int i=1;i<=size[k];i++)...

最外面的一个k类似于普通背包的第几个物品，最里面一层枚举组内的物品，就保证了每组最多选一个（因为是从先从大到小枚举体积(j)，那么对于(f[j],f[j-c_i])这些只能由上一组的状态转移过来）

泛化物品：每个物品可能没有固定的价值/体积，价值(V)是关于体积的函数(f(W))

数位DP

ll dfs(int x,int pre,int st,……,int lead,int limit){
	if(!x) return st;
	if((dp[x][pre][st]…[]!=-1&&!limit&&!lead))return dp[x][pre][st]…[];
	ll ret=0;
	int mx=limit?a[x]:9;
	rep(i,0,mx){
        //有前导0并且当前位也是前导0
		if(!i&&lead) ret+=dfs(……,……,……,i==mx&&limit);
        //有前导0但当前位不是前导0，当前位就是最高位
		else if(i&&lead) ret+=dfs(……,……,……,i==mx&&limit); 
		else if(根据题意而定的判断) ret+=dfs(……,……,……,i==mx&&limit);
	}
	if(!limit&&!lead) dp[x][pre][st]……[……]=ret;
	return ret;
}
ll solve(ll x){
	len=0;
	while(x) a[++len]=x%10,x/=10;
	memset(dp,-1,sizeof dp);//初始化-1（因为有可能某些情况下的方案数是0）
	return dfs(……,……,……,……);//进入记搜
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%lld%lld",&l,&r);
	    if(l) printf("%lld",solve(r)-solve(l-1));//[l,r](l!=0)
	    else printf("%lld",solve(r)-solve(l));//从0开始要特判,按情况看看要不要加别的
	}
	return 0;
}

题

线性

http://poj.org/problem?id=2279

$ N$个学生合影，站成左端对齐的 (k)排，每排分别有(N1,N2,dots,N_k)个人。 ((N1≥N2≥…≥Nk))

第1排站在最后边，第 (k) 排站在最前边。 学生的身高互不相同，把他们从高到底依次标记为(1,2,…,N)。

在合影时要求每一排从左到右身高递减，每一列从后到前身高也递减。问一共有多少种安排合影位置的方案？((kleq 5,sum N_ileq 30))

线性dp容易给出一个，以及注意一种(O(30^5))的做法，但是这题会炸空间。

这个背景是和整数拆分有关的【杨氏矩阵】，记(n=sum N_i)，每个位置((i,j))和所有它右边和下方（如果有）的格子个数（包括自己）称为这个“钩子”的长度，这题对应的答案就是(n!/Pi)钩子长度，证明不会。

https://www.acwing.com/problem/content/274/

最长上升公共子序列，LIS是(f[i])记录以(i)为结尾的LIS，LCS则是记录(1-i)和(1-j)的，这里就考虑综合起来，(f[i][j])表示以(s[1,dots,i])，以(t[j])为结尾的LCIS的长度，类似LCS，如果(a[i]
eq b[j])，直接(f[i][j]=f[i-1][j])，否则如果(a[i]=b[j])，就有转移(egin{aligned}f[i][j]=max_{k=1,dots,j-1,b[k]<b[j]}(f[i-1][k])+1end{aligned})，又(b[j]=a[i])，下面改成(b[k]<a[i])，原本(O(n))的转移就可以优化了：枚举(i)之后对固定的(i)，枚举(j)的同时更新这个(max)，整体就能做到(O(n^2))。

https://www.acwing.com/problem/content/275/

给(a[])，需要构造一个单调不减或者单调不增的(b[])，最小化(sum |a_i-b_i|,nleq 2000)。

容易想到先考虑单调不增或者单调不减的其中一种情况，另一种把(a[])翻转过来再做一遍就行。就以考虑单调不减的序列为例，用(f[i][j])表示前(i)个，以(j)作为(b[])的结尾的最小答案，这样就有(egin{aligned}f[i][j]=min_{k=1,dots,j}f[i-1][j]+|a_i-j|end{aligned})，不过这样值域有点大，注意到任何一个(b[j])的取值，一定是取(a[])中的某个项，不然就浪费了，所以可以离散化一下，复杂度(O(n^3))，进一步，这题其实和上题类似，对于一个固定的(i)，决策集合只增不减，(O(n))的转移可以和枚举(j)一起进行，时间复杂度(O(n^2))。

关于(b[j])一定取(a[])中的某个值可以考虑一个数学归纳：假设对(1,dots,k-1)成立，对于(i=k)来说，如果(b[k-1]leq a[k])，直接构造(b[k]=a[k])就做到了最优的；否则考虑让(b[k]=b[k-1])，根据归纳我们能够说明(b[k-1])取的是(a[1,dots,k-1])，但这还不够，我们需要证明我们取(b[k]=b[k-1])这种决策能够达到最优，想一下也显然，考虑从(i=k)往前的一段区间([j,k])，这一段的(b[i])都取得相同的(v)，那这就变成给一个(a[])，最小化(sum |a_i-v|)的问题了，这个问题很经典，显然最优情况下的(v)能够取得到(a[])中的值。

https://www.acwing.com/problem/content/276/

(L)个点的有向往全图，每条边有边权（即对应(u o v)的代价），有3个人一开始分别在1,2,3处，(1-n)个时刻，每个时刻需要有一个人在(p_i)这个点，同一个时刻只有同一个时刻一个点不能有多个人，问满足所有需求需要的最小代价。(Lleq 200,nleq 1000)。

考虑DP还是先想怎么记录状态，依然先考虑最暴力的，三个人的位置肯定要能够被记录进去，同时还要记录处理到了哪个时刻，于是就有了(O(L^3n))级别的状态，太大了没法跑。

很套路地想怎么去掉一些状态，任意一个时刻一定会有一个人处于(p_i)的位置，于是就可以去掉一个(L)，比如(f[i][a][b])表示到时刻(i)，一个人在(p[i])，另外两个人分别在(a,b)这两个位置，转移也很好想，即(p_i/a/b o p_{i+1})三种转移方式，实现的时候判定一下状态合法即可。

背包

https://codeforces.com/problemset/problem/19/B

Bob拿着(n)件商品在收银台付款，扫描第(i)件商品需要(t_i)的时间，第(i)件的价格为(c_i)，在扫描的时候可以选择偷走一些商品，偷走一个商品需要1个单位的时间，问最少花多少钱能获得所有商品。(nleq 2000,t_ileq 2000)

相当于把商品划分成两个集合(S,T)，满足(|T|leq sum_{S}t_i)，使得(sum_{S}c_i)最小，左边的式子稍微变形会得到(sum_{T}t_i+|T|=sum_{T}(t_i+1)leq sum t_i)，这就很像背包了：反着考虑获得哪些物品不要花钱，总容量为(sum t_i)，选择一件物品不花钱得到的代价是(t_i+1)，这样一个01背包问题，但是复杂度会达到(O(nt^2)=O(n^3))，接受不了。

不过顺着这个背包的思路继续想，选择花钱买一件物品相当于多获得一个(t_i+1)的体积，对应的付出(c_i)的代价，最终目标是获得所有物品，即(sum_{S}t_i+1geq n)，于是又是一个背包：选择花钱购买一些物品，使得这些物品的体积之和超过(n)，求最小的代价。同样的问题又来了，这样做背包的体积上界是多少？如果还是(O(n^2))级别的话这个优化就没什么用了：仔细想一下上界不会很大，在一系列决策之后如果当前的(sum t_i+)已经超过了(n)，那后面的一定不会继续选择购买，所以最大的情况一定是从一个小于(n)的体积跨越到一个大于(n)的体积，对应的上界就是(n-1+(v_{max}+1)=n+v_{max})了。

https://www.luogu.com.cn/problem/P4141

背包问题变形，(n)个物品，需要回答如果没有第(i)个物品的时候，恰好装满容量为(x=1,dots m)的背包需要多少代价？(n,mleq 2000)。

原问题是(dp[i][j]=dp[i-1][j]+dp[i-1][j-v[i]])和(dp[0][0]=1)，暴力做是直接(O(n^2m))的，先处理处没有第一个物品的答案，然后考虑如何给dp删除一个物品和添加物品。

按照滚动数组得到的dp数组考虑，注意到物品顺序不影响答案，假设当前得到的是(f[0,dots,m])，删去物品(i)之后的答案是(g[1,dots,m])，则有当(j<v[i])时，(f[j]=g[j])，当(jgeq v[i])时(f[j]=g[j]+g[j-v[i]])，于是就能从小到大反推出(g[])，这样每一次只需要(O(m))的代价计算删除和加入一个物品的答案。

rep(i,2,n){ 
    rep(j,0,w[i]-1)g[j]=f[j];
    rep(j,w[i],m)g[j]=(f[j]-g[j-w[i]]+10)%10;

    rep(j,0,m)f[j]=g[j];
    for(int j=m;j>=w[i-1];j--)upd(f[j],f[j-w[i-1]]);
    rep(j,1,m)printf("%c",f[j]+'0');
    puts("");
}

https://www.luogu.com.cn/problem/P1877

01背包变形，(dp[i][j])有(dp[i-1][j-c[i]])和(dp[i-1][j+c[i]])两个转移。

https://www.luogu.com.cn/problem/P1509

二维背包变形，两个代价（rmb和rp）以及两个收益（在泡到最多MM的前提下时间最小），可以考虑两个dp数组，在MM最多的前提下再比较第二维，或者像我在实现的时候直接开个struct来存dp，重载一个比较函数。

https://www.luogu.com.cn/problem/P3985

二维背包变形，一开始理解错题意，以为是DP的时候多带一个极差(leq3)的限制，后面发现原来是给的数据保证极差(leq 3)，那就好做了，考虑最后选择的物品的集合是(S)，最后要(sum_{iin S} v_ileq W)，取(X=min_i(v_i))，式子变成(X|S|+sum_{iin S}(v_i-X)leq W)，考虑个双重限制的背包：一个是(v_iin{0,1,2,3})，和第二维代价：每选一个物品代价是1，先对这个二维背包进行DP，然后再统计符合条件的答案。

https://www.luogu.com.cn/problem/P1455

并查集维护连通块，然后直接对每一个联通块01背包

https://www.luogu.com.cn/problem/P1858

(K)个人，每个人有一个背包，容量都是(V)，(N)件物品，现在要每个人都能恰好装满背包，并且任意两个人选的物品不完全相同，所有人价值之和的最大(Kleq 50,Vleq 5000,Nleq 200)。

发现相当于在求一个01背包要求完全装满的前(K)大值，前(K)大的处理一般是把普通的DP式子转化成一个单调队列来维护，转移变成(O(k))地归并状态。

rep(i,1,n)per(j,V,v[i]){
	tmp.clear();
	for(auto itr:f[j])tmp.pb(itr);
	f[j].clear();

    int p=0,q=0;
    while((p<tmp.size()||q<f[j-v[i]].size())&&(p+q<=k)){
        int sp=tmp.size(),sq=f[j-v[i]].size();
        if(q>=sq||(p<sp&&q<sq&&tmp[p]>w[i]+f[j-v[i]][q]))f[j].pb(tmp[p++]);
        else f[j].pb(w[i]+f[j-v[i]][q++]);
    }
}

https://www.luogu.com.cn/problem/P1776

完全背包问题，带log的和单调队列优化的都能过，暴力的还没试过（

https://www.luogu.com.cn/problem/P5322

（一道评价还不错的dp题）手上的士兵很像背包的容量，而对于每座城堡来说又可以看成一个类似于“物品”的东西，就转换成了一个类似01背包的问题，但是因为有多个玩家，我们对每座城堡所有玩家的(a_i)升序排列，然后在从大到小枚举体积(j)的时候直接f[j]=max(f[j],f[j-2*a[i]-1])+i 就行（因为排序之后就保证了不会在同一个(i)内部重复计算。

https://www.luogu.com.cn/problem/P1782

多重背包+泛化背包，不过这个泛化背包的处理也很暴力…以及这题有点卡常

单调栈/单调队列

https://www.luogu.com.cn/problem/P2254

给你一张地图，一些地方不能走，输入初始位置，(K)段时间，每段时间内要么只能往指定的方向走，要么不走，问最远能走多长的路径。(n,m,kleq 200)

用(f[i][j][k])表示第(k)段时间走完之后在((i,j))处的答案，暴力转移(egin{aligned}f[i][j][k]=max_{t=0}^{ed_k-st_k+1}{f[i-tDelta x][j-tDelta y][k-1]+t}end{aligned})，这样就得到了一个四次方的DP，但是应该是数据太水（以及可能因为是十几年前的题了，当时测评机没这么快）…这么个大暴力就过了这题：

rep(k,1,K)rep(i,1,n)rep(j,1,m)if(avl[i][j]){
    int mx=-INF;
    rep(t,0,ed[k]-st[k]+1){
        int cx=i-t*di[d[k]],cy=j-t*dj[d[k]];
        if(!check(cx,cy))break;
        if(f[cx][cy][k-1]==-INF)continue;
        mx=max(mx,f[cx][cy][k-1]+t);
    }
    f[i][j][k]=mx;
}

不过还是来优化转移过程，其实(Delta x,Delta y)里面会有一个是0，假设(j)定下来，(i)是这次动的方向，我们对于每个确定的(k,j)，其实可以(O(n))对

(f[i][j][k]=max_{t=0}^{len}{f[i-tDelta x][j][k-1]+t})进行转移：假设这个(d[k])意味着(i)只能增大，那我就从1枚举(i)，用单调队列维护(f[i-tDelta x][j][k-1]-t)，每次再用(Q.front()+t)来更新答案（注意前面单调队列里维护的是(-t)，因为原来dp式子里的(t)的含义其实是两个位置的距离，相当于是(t_{当前}-t_{从哪转移来})）

数位

http://acm.hdu.edu.cn/showproblem.php?pid=2089

数位上不能有连续的62，以及不能有4。

https://www.luogu.com.cn/problem/P2602

统计([l,r])内所有数码出现的次数，一位一位数码考虑，要算数位出现的次数，答案也丢到dfs里面来跑，状态多记几个不会爆的…

ll dfs(int x,int cnt,int D,bool limit,bool lead)
{
	if(~f[x][cnt][limit][lead])return f[x][cnt][limit][lead];
	if(!x)return f[x][cnt][limit][lead]=cnt;
	int mx=limit?digit[x]:9;
	ll ret=0;
	rep(i,0,mx)
	{
		int cnt2=cnt;
		if(i)cnt2+=(i==D);
		else cnt2+=(!lead&&i==D);
		ret+=dfs(x-1,cnt2,D,limit&&i==digit[x],lead&&!i);
	}
	return f[x][cnt][limit][lead]=ret;
}

https://codeforces.com/problemset/problem/276/D

考虑(a,bin [l,r])，问(aoplus b)的最大值，(l,rleq 10^{18})。

异或想到考虑二进制，但是不太会考虑，那就大力枚举，数位dp不就是干这种事情嘛？

(f[x][l1][r1][l2][r2])表示从高往低考虑到第(x)位，(l1,r1)表示对(a)的约束，同样(l2,r2)是对(b)的约束。

if(!x)return 0;
if(~f[x][l1][r1][l2][r2])return f[x][l1][r1][l2][r2];
ll ans=0;
//l1,r1 means first number's upper and lower bound 
rep(i,l1?L[x]:0,r1?R[x]:1)
    rep(j,l2?L[x]:0,r2?R[x]:1){
        ll t=i^j;t<<=(x-1);
        t+=dfs(x-1,l1&&i==L[x],r1&&i==R[x],l2&&j==L[x],r2&&j==R[x]);
        ans=max(ans,t);
    }
return f[x][l1][r1][l2][r2]=ans;

树形

https://www.luogu.com.cn/problem/P1352

入门题

http://acm.hdu.edu.cn/showproblem.php?pid=2196

对树上每个点求它到哪个点距离最远，一个(O(nlog n))的做法是先(O(n))求出直径(r_1,r_2)，那么每个点(x)的答案就是(max{dis(r_1.x).dis(r_2.x)})，注意这题有多组数据（以及一开始以为没清空干净数组，疯狂MLE/TLE）。