集训笔记

巨弱 代码 笔记

模拟只会猜题意,贪心只能过样例。
数学上来先打表,ＤＰ一般看规律。
组合数学靠运气,计算几何瞎暴力。
图论一顿套模板,数论只会ＧＣＤ。

QAQ在场的各位都比我强……如有谬误欢迎指正!
因为菜作者买不起图床，图已经都挂了……大家猜猜就好了……

目录

day1

倍增

以下文章中的倍增代码中的^全都是乘方的意思……不是异或qwq不能直接复制啊orz

定义：以F[i][j]表示，以i位置出发2^j个位置的状态
【为什么只乘2？】如果按照k来查的话，实际上为(k-1)logk的复杂度，可证明k=2的时候复杂度最小2333333

应用1 ST表

应用：ST表（用来解决RMQ问题：从i到i+2^j-1这2^j个位置的最大值）//其实可以用线段树的……但是ST表好写qwq
初始化：f[i][0]=z[i];
转移：f[i][j]=max[f[i][j-1],f[i+2^(j-1)][j-1]);（相当准确的二分）
限制：不能算区间和：中间有重复的部分
不支持修改。
询问：两种情况：
n个数，m个询问，询问l->r最大值
1）若区间长度正好是2^k，那么就直接访问f[l][k];
2）若区间长度是2^k+p（p<2^k)，则当前最大值=max(f[l][k]，f[r-2^k+1][k]）；

//build
for(int a=1;a<=n;a++) f[a][0]=z[a];
for(int j=1;j<=logn;j++)
{
    for(int i=1;i+z^j-1<=n;i++)
        f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1]);、
        //乘方是伪代码！
}
//solve
ans=max(f[l][k]，f[r-2^k+1][k]）；
*/

应用2 LCA

树上倍增LCA:

有一种叫做动态树的结构（LCT）可以解决这个问题，树链剖分，于是能够动态修改，noip用不着，但是还是要好好学学……

求最近公共祖先。
f[i][j]表示从树上编号为i的点向上走2^j步会走到哪个点
j大概20-30就行0 0 2^j>点数差不多就行……
初始化：f[i][0]=father[i];
转移：f[i][j]=f[f[i][j-1]][j-1];
从i往上走2^(j-1)到的那个点再往上走2^(j-1)步到的点即为从i往上走2^j到的点
tarjan是线性的。。。为什么不用tarjan呢……
询问：得到两个点p1,p2；
首先建树的时候要记录一下深度。
两种情况：
1）depth[p1]==depth[p2]，则具有性质：往上走同样的距离，深度仍然相同,如果走到了最近公共祖先，那么再往上走，就一定有p1==p2;

for(int x=19;x>=0;x--)
    if(f[p1][x]!=f[p2][x])
        p1=f[p1][x];
        p2=f[p2][x];
    //如果没有走到公共祖先处，就使劲往上跳
    //因为x的值是逆序的，所以会尽可能地上跳，接下来的长度一定不大于2^(x-1)

2）depth[p1]!=depth[p2]
若P1深度比较深，就让P1上跳，跳到深度一样的地方。
如何利用f数组在倍增上跳呢?
step=depth[p1]-depth[p2];
举例：step=13,二进制中：1101：先走八步，再走四步，再走一步就可以了

int get_lca(int p1,int p2)
{
    if(dpeth[p1]<depth[p2]) swap(p1,p2);
    for(int x=19;x>=0;x--)
    {
    if((2^x)<=depth[p1]-depth[p2]) p1=f[p1][x];
    }
}

应用3 快速幂【也有分治】

求A^x；[O(logx)]
如果每次把a*a*a*a*a*……真的好麻烦qwq还费时间
所以如果我们要求x(x=2*k)个a的乘积，就可以分解为x/2个a的乘积的平方。就省去了一半的计算量~
x如果是奇数，就在原先的基础上再乘一次a就行了。递归代码可以改循环~

int ksm(int a,int x,int mod)
{
    ans=1;
    while(x)
    {
        if (x&1) ans=(ans*a) % mod;//位运算：x&1==1则x为奇数
        A=(a*a) % mod;
        x>>1;//位运算，右移一位，即将X除以2
    }
}

引申：快速乘法
求a*x=a+a+a+a+……
把ksm里面所有的乘号都变成加号就行了- =

分治

应用1 二分查找

给定一个排序后的数组，查询某个数是否在数组中

bool find(int x)
{
    l=0,r=n;
    while(l+1!=r)
    {
        m=(l+r)>>1;
        if(z[m]>=x) r=m;
        else l=m;
    }
}

可以用lowerbound或者upperbound

应用2 归并排序(nlogn)

先砍成两半再说！
把这边归并排序 那边归并排序 搞俩指针转悠转悠- = 把小值排到上面区间的下一个就行了……

应用3 快速排序(nlogn)

sort【快排】（c艹的特性：不会退化成n*n，有奇怪的优化，而且比下面三个快……）
qsort(最坏会退化成n*n，最好n，期望nlogn)
merge_sort【归并排序】(无论何时都是nlogn，稳定）
heap_sort【堆排】（同上）

贪心

以某种方式将所有物品排序
排序后按照从小到大进行选择
给你n个数，要求选出K个数使他们的和最大

[noip2012] 国王游戏
Description
恰逢 H 国国庆，国王邀请n位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序， 使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。
Input
第一行包含一个整数 n，表示大臣的人数。
第二行包含两个整数a和b，之间用一个空格隔开，分别表示国王左手和右手上的整数。 接下来n行，每行包含两个整数a和b，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。
Output
输出只有一行，包含一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
Sample Input
3
1 1
2 3
7 4
4 6
Sample Output
2
Hint
【输入输出样例说明】
按1、2、3号大臣这样排列队伍，获得奖赏最多的大臣所获得金币数为2；
按1、3、2这样排列队伍，获得奖赏最多的大臣所获得金币数为2；
按2、1、3这样排列队伍，获得奖赏最多的大臣所获得金币数为2；
按2、3、1这样排列队伍，获得奖赏最多的大臣所获得金币数为9；
按3、1、2这样排列队伍，获得奖赏最多的大臣所获得金币数为2；
按3、2、1这样排列队伍，获得奖赏最多的大臣所获得金币数为9。
因此，奖赏最多的大臣最少获得 2 个金币，答案输出 2。
对于 20%的数据，有 1≤ n≤ 10，0 < a、b < 8；
对于 40%的数据，有 1≤ n≤20，0 < a、b < 8；
对于 60%的数据，有 1≤ n≤100； 对于 60%的数据，保证答案不超过 10^9；
对于 100%的数据，有 1 ≤ n ≤1,000，0 < a、b < 10000。

只考虑两个人
第i个人左右手数字：l[i],r[i];第二个人：l[i+1],r[i+1];两人金币数为w[i],w[i+1];
记P[i]=l[1]*l[2]l[3]...*l[i]
可得：
w[i]=P[i-1]/r[i];
w[i+1]=P[i]/r[i+1];
又P[i]=P[i-1]*l[i]；
那么 w[i+1]=P[i-1]*l[i]/r[i+1]=w[i]*l[i]*r[i]/r[i+1]；
于是乎 按a[i]*b[i]为关键字从小到大排序就好啦。
乘除法都要写高精度，且答案有10000多位。//国王真有钱

所有的贪心题都可以用拟证来证明

搜索

两种不同的搜索问题
1.最优性
2.计数

两种不同的搜索方法
1.DFS
2.BFS

剪枝
卡时：（一般不用在树上）（OJ上不建议这么做）看到快超时的时候就退出程序，从只能得零分变成了至少得零分了……

include <ctime>//去官网看能不能用，否则就会变成至多零分了……
void dfs()
{
    if(clock()-t>=1998)//以毫秒为单位
    {
        shuchujie();exit(0);
    }
}
int main()
{
    t=clock();
}

数据结构维护（一般不会出到这么难）

搜索的优化技巧
1.剪枝
2.BFS：双向搜索meet in the middle（前提条件：必须知道你最终需要的状态长什么样）
从初始状态扩展出来n个状态后，不再扩展出n*n个状态，而是从最后一个在扩展出来n个。再从原来的方向搜索。从原来的O(X)变成O(sqrt(X))
3.计数问题：重复结构利用
4.最优化问题：卡时
5.数据结构优化

搜索
N皇后问题[状压DP优化]
数独问题[卡时] 启发式搜索：从个数最少的开始搜索（跳舞链dancing links是啥？）
noip 2012 mayann

奇怪的东西
读入优化：(读int超快！)
int getint()
C=' ';
while(c<'0' || c>'9') c=getchar();
X=0;
while(c>='0' && c<='9') X=X*10+c-'0',c=getchar()

模拟

今天模拟三道题，我真是太菜了……
第一题：
枚举换哪几个格子，真的就是无脑枚举模拟，我也不知道为什么我居然错了，就这样吧ovo
（这种题能够快速提高代码能力，建议闲的没事多做做）
第二题：
二分答案+暴力
比如知道当前二分出来的答案是m，要求出是否存在这样一个矩阵，使其四个点都大于等于m。往右延伸一定的距离，再往下延伸，就能确定整个矩形，算出来最小值，和答案进行对比就可以了- =
可以这么操作：把大于等于r的值都变成0，小于r的变成0，可以等价为是否存在矩阵是四个点都是1。可以提前预处理出来哪些位置是1，就不需要枚举其它位置了。

还有另外一个方法：
将所有的点权值从大到小一个一个加到矩形中，如果出现了新的矩形就输出
第三题：
杨辉三角…………………………生气

杨辉三角的补充：

组合数：从n个物体中选m个的方案数
Cnm=n!/(m!(n-m)!)
Cnm=C(n-1)(m-1)+C(n-i)(m)//可以不断拆开
Cnm=sigma(j=0->i) C(n-2)(m-i+j)*cij;
cnm=cn(n-m)
如果把它们都列出来，就是一个杨辉三角，是右上方和左上方两个数的和

lucas:
cnm%p 可以逆元，或者把n,m变成p进制的数，则cnm%p=cn1m1*cn2m2*cn3m3%p

ummmm我觉得我现在做题还比较稚嫩……就像我都想到正解或者接近正解，就是不敢写……要么就写挂，果然要锻炼代码能力啊……

day 2

素数的判定

1)弱智才会用的办法

bool prime(int x)
{
    if (x<2) return 0;
    for(int a=2;a*a<x;a++) if(x % a==0) return 0;
    return 1;
}

2)费马小定理

p为一个素数且p不是a的倍数，则a^(p-1)=1(mod p);[不能反推]
多次选取a，检验p是否满足费马小定理。
O(klogp)
卡迈尔数

3)miller-rabin(MR定理）

如果n为素数，取a < n,设n-1=d*2^r,则要么a^d≡1(mod n)，要么30<=i < r,s.t.a ^(d*s^t)≡-1(mod n)

int prime=[3,7,11,23,37];
bool miller_rabin(int x)
{
    n-1=d*2^r;
    for(int a=1;a<=5;a++)
    {
        if(ksm(a,d) %n !=1)
        {
            for(int i=0;i<r;i++)
            {
                if(ksm(a,d*2^i)%n==-1) return 1;
            }
            return 0;
        }
    }
}

钟神：“背结论吧。”

4)筛法

用来处理连续区间内有哪些质数。
a.非线性筛法(nlogn=1/1+1/2+1/3+···+1/n)
质数的倍数一定是合数。

bool not_prime[1000005];
not_prime[1]=true;
for(int a=2;a<=n;a++）
{
    if(!not_prime[a]) for(int b=a+a;b<=n;b+=a) not_prime[b]=true;//如果有那个if优化的话，就是nloglogn
}

b.线性筛法（欧拉筛法）
每个合数都由它最小的质因数筛掉。一个数会被拆成几个质数相乘，最小的质数就直接筛了，就避免了重复筛的过程。接近于O(n)

memset(notprime,0,sizeof(notprime)),notprime[1]=true;
for(int i=2;i<=n;i++)
{
if(!notprime[i]) prime[++ prime_count]=i;
    for(int j=1;j<=prime_count;++j)
    {
        if(prime[j]*i>n) break;
        not_prime[prime[j]*i]=true;//用来筛质数的倍数的数
        if(i%prime[j]==0) break;//保证了只会找到最小的质因子来筛掉它
    }
}

欧几里得定理：

求n个不超过m的正整数复杂度：O(n+logm);
通过辗转相除法求最大公因数。

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;//一行代码就是爽
}

扩展欧几里得定理

欢迎访问我的博客，讲的和钟神一样清晰233
扩展欧几里得算法

求解同余方程

题目描述求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。
输入数据输入只有一行，包含两个正整数 a, b，用一个空格隔开。
输出数据输出只有一行，包含一个正整数 x0，即最小正整数解。输入数据保证一定有解。
输入样例3 10
输出样例7
数据范围
对于 40%的数据，2 ≤b≤ 1,000；
对于 60%的数据，2 ≤b≤ 50,000,000；
对于 100%的数据，2 ≤a, b≤ 2,000,000,000。

ax%b=1 <=> ax-by=1;
可由此求出一组x,y的解，转移得到正整数最小解就行啦

求解一次同余式组：中国剩余定理

有一个数 x≡a1(b1 mod p1),x≡a2(mod p2),x≡a3(mod p3)……,x≡ak(mod pk);
求解最小x。
x=k1p1+a1,x=k2p2+a2……
k1p1+a1=k2p2+a2 -> k1p1-k2p2=a2-a1;
将好多好多的这样的方程加在一起。

大数翻倍法

x=a1(mod p1);
x=a2(mod p2);
假设P1 < P2；
复杂度O(min(p1,p2));

int fanbei(int a1,int p1,int a2,int p2)//p1<p2
{
ans=a2;
while(ans % p1 != a1) ans+=p2;
return ans;
}

大体的意思就是，找到一个最大的P，然后不断翻倍，使它能够整除其它所有的P

逆元

在模的意义下通过逆元也能做除法。
如果gcd(a,m)=1,且存在唯一的b，使得a*b≡1(mod m)且1<=b < m,则b为a在模m意义下的逆元
当m为质数的时候，直接使用费马小定理 a^(p-1)≡1
m非质数时，使用欧拉定理 a^φ(m)≡1
φ(m)：欧拉函数，表示小于等于m的质数的个数

积性函数

如果对于(n,m)=1,有f(nm)=f(n)f(m)，则称f为积性函数
σ(n)=Σd|n d 从1到n的加和
τ(n)=Σd|n 1 n的因子个数
φ(n) 欧拉函数 1-n当中与n互质的数的个数 ϕ(n)=n∗∏(pi−1)/pi（∏：乘积）
μ(n) 莫比乌斯函数 n=p1^k1*p2^k2*p3^k3……

当n=1时，μ(n)=1
当k1=k2=k3=……=kr=1时，μ(n)=(-1)^r;
否则μ(n)=0;

在数论的容斥原理中多有使用。
求积性函数只需要在线性筛中加上函数就行。
举例子：欧拉函数

memset(notprime,0,sizeof(notprime)),notprime[1]=true;
for(int i=2;i<=n;i++)
{
    if(!notprime[i])
    {
        prime[++ prime_count]=i;
        phi[i]=i-1;
    }
    for(int j=1;j<=prime_count;++j)
    {
        if(prime[j]*i>n) break;
        not_prime[prime[j]*i]=true;
        if(i%prime[j]!=0)//积性必须满足gcd(n,m)=1
        {
            phi[prime[j]*i]=phi[prime[j]]*phi[i];//a与b互质的话，a+b与b也互质
        }
        else phi[i*prime[j]]=phi[i]*prime[j];
        if(i%prime[j]==0) break;
    }
}

留着看：欧拉函数

例题：求a^x≡b(mod m)的最小正整数解。
BSGS（北上广深）算法：
a^φ(m)≡1(mod m),所以解一定在a^1,a^2,a^3……a^m之间
可以每次两个两个枚举，如果没有答案就乘上a^2,再继续枚举下去。
最高效的方式：k=sqrt(m)，写成一个k*k的矩阵形式

每行询问klogk，第一行排序klongk，O(sqrt(m)log(m)）.
在每一行是否出现，可以直接通过除以a^nk（乘法逆元），转移到第一行

作业：给一个n,m,for(int i=1,i<=n;i++) for(int j=1;j<=m;j++) 求Σgcd(i,j);

概率

基本知识

Pr[i]表示事件i发生的概率 Σi=1->N Pr[i]=1； xi表示事件i的权重 E[x]=Σi=1->N Pr[i]*xi 有x个人没有人生日相同的概率：366/366+365/366+364/366……+366-x+1/366

对于独立事件i和j，Pr[i^j]=pr[i]*pr[j] 事件i和事件j的期望是可加的。

条件概率： 当事件j已经发生时，事件i发生的几率 pr[i|j]=pr[i^j]/pr[j] 一个有趣的结论: 当太阳已经从东边升起n天后，第n+1天从东边升起的概率：(n+1)/(n+2)

题目

1)problem 1
甲乙面前三瓶药，两瓶毒药，每人喝一瓶。
甲喝了一瓶，挂掉了
为了活下去，乙应该喝手上的这瓶，还是另外剩下的一瓶呢？
喝哪个都一样，因为乙不知道哪个有毒。

2)problem 2

小胡站在原点，手里拿着两枚硬币。抛第一枚硬币正面向上的概率为𝑝，第二枚正面向上的概率为𝑞。
小胡开始抛第一枚硬币，每次抛到反面小胡就向𝑥轴正方向走一步，直到抛到正面。
接下来小胡继续抛第一枚硬币，每次抛到反面小胡就向𝑦轴正方向走一步，直到抛到正面。
现在小胡想回来了，于是他开始抛第二枚硬币，如果小胡抛到正面小胡就向𝑥轴的负方向走一步，否则小胡就向𝑦轴的负方向走一步。
现在小胡想知道他在往回走的时候经过原点的概率是多少呢？

假设小胡走到(x,y)又回到原点。首先往x正方向走x步又抛到正面的概率是p*(1-p)^x,在往y轴正方向走y步的又抛到正面的概率是(1-p)^y*p。往回走的时候：往X负方向走x步的概率是q^x,往Y负方向走y步的概率是(1-q)^y。总的概率是：
p*(1-p)^x*(1-p)^y*p*q^x*(1-q)^y=p^2*(1-p)^(x+y)q^x(1-q)^y;
一共走x+y步，其中不知道x有几步，于是我们要枚举x+y和x。每对x+y,x都有c(x+y)x种方式。在原来的概率上加上组合数就行啦。
最后的概率：

化简以后:

注意这个公式的运用：

2.3) problem 2.3

小葱想要过河，过河有两条路
一条路有100个石头，每个石头有1/100的概率会挂掉
一条路有1000个石头，每个石头有1/1000的概率会挂掉
小葱应该走哪边呢？
请勿使用计算器

显然：

3) problem 3
这道题被抛弃了……

4) problem 4

小泽在数轴上的0点处
小泽每次有𝑟的概率向右走，有1−𝑟的概率向左走
问小泽走到−1处的概率

试着枚举步数www

PS：刚刚翻到一个超棒的浅谈卡特兰数

如果按照上面那种一步步加上来的办法，特别麻烦……
所以换个思路，设概率试试。
设从x出发到达x-1的概率为p,第一步向左的概率是1-r,第一步向右到x，再从x到x-1的概率是rp^2。则有p=(1-r)+rp^2。
解得：
p=1 (r<=1/2),
p=(1-r)/r (r>1/2);

5) problem 5

小胡有一棵一个点的树，小胡会给这个点浇水，于是这个点会有𝑝的概率长出两个儿子节点。
每次长出新的节点之后，小胡又会给新的节点浇水，它们也都有𝑝的概率长出两个新的儿子节点。
小胡不希望自己被累死，所以小胡希望知道这棵树的大小是有限的的概率。

这道题和problem4是一样的……

6) problem 6
老师又弃题啦QAQ

给一堆点的坐标。在平面内画个圆，把所有的点都包含进去，问最小半径

第一种方法：
三点可以确定一个圆，所以暴力方法：枚举三个点，再把剩下的点一个一个扔进去，看看在不在圆里面
O(n^4)
如何优化？
举个例子，通过a,b,c三个点你确定了一个圆，圆包含x,y,z三点，但是不符合条件，于是你开始重新枚举。但是未来就没有枚举x,y,z的必要了……这样就浪费了很多。
那么不如一个个往里面加点，加点后再扩张~

for（int a=1;a<=n;a++)
{
    if(!in(p[a])) circle=cir(p[a]);
    for(int b=1;b<=a;b++)
    {
        if(!in(p[b])) circle=cir(p[a],p[b]);
        for(int c=1;c<=b;c++)
        {
            if(!in(c)) circle=cir(p[a],p[b],p[c]);
        }
    }
}

第二种方法
c++有个函数叫random_shuffle，作用是随机打乱n个点的顺序。
可以将它优化到O(n)。
随机选三个点形成一个圆。
于是接下里的点进入下面两个循环的概率实际上很小233所以复杂度就会变得很玄学很诡异……

代数

排列和逆序对

逆序对：对于一个排列a1,a2,a3……an，若存在一个1<=i < j<=n，存在ai > aj，则这个有序对成为一个逆序对，也称为逆序数。
对换：在一个排列中，对换其中某两个数，其余的数不动，得到另一个排列，这种操作称为一个对换。
奇偶排列：如果一个排列的逆序数是偶数，则称此排列为偶排列，否则称为奇排列。

行列式

我没有弄明白这个东西的原理和用途。希望能有大佬给我一点指导
QQ:1183940941

矩阵

乘法
定义：设A=aij(m*r),B=bij(r*n),则矩阵C=cij(m*n).其中cij=ai1*b1j+ai2*b2j+……+ain*bnj。
C称为𝐴与𝐵的乘积，记做𝐶=𝐴𝐵
第一个矩阵的列数必须等于第二个矩阵的行数！

矩阵乘法运算律

特殊的矩阵
零矩阵

0 0 0
0 0 0
0 0 0

对角矩阵

1 0 0
0 0 0
0 0 3

单位矩阵

1 0 0
0 1 0
0 0 1

上三角矩阵

1 2 3
0 4 5
0 0 6

下三角矩阵

1 0 0
2 3 0
4 5 6

对称矩阵

1 2 6
2 3 5
6 5 7

递推与矩阵
斐波那契和矩阵乘法的关系？
|fn-1 fn| × |0 1| =|fn   fn+fn-1|
                 |1 1|           (fn+1)
如果换了一个递推公式，要怎么写这个矩阵呢？
f(n)=af(n-1)+bf(n-2);
|fn fn-1| × |w x|=[fn+1 fn];
                  |y z|
通过矩阵乘法的特点，可得到关系式：
fn+1=wfn+yfn-1
fn=xfn+zfn-1
于是可得：a=w,b=y,x=1,z=0;
于是原矩阵中值可以由上面的等值代替啦。

矩阵在解方程上的应用
一般线性方程组：

a11x1+a12x2+……+a1nxn=b1
a21x1+a22x2+……+a2nxn=b2
···
an1x1+an2x2+……+annxn=bn

高斯消元法
即加减消元法。在计算机中，方法则不同。

x1+x2+x3=6
x1+2x2+3x3=9
x1+4x2+9x3=36

将系数变成一个矩阵

1 1 1 6
1 2 3 9
1 4 9 36

用第二行，第三行分别减去第一行得到

1 1 1 6
0 1 2 3
0 3 8 30

用第三行减去三倍的第二行得到

1 1 1 6
0 1 2 3
0 0 2 21

最后一行21/2=x3;
倒数第二行x2+2x3=3，解得x2=-18;
同理可得x1值。

如果当前方程系数是0，那就在下面找个不是0的跟它换一下就好了……

//矩阵：m
for(int a=1;a<=n;a++)
{
    if(fabs(m[a][a])<=eps)
    {
        for(int b=a+1;b<=n;b++)
        {
            if(fabs(m[b][a])>eps) swap(m[a],m[b]);//fabs用于浮点数,m[a],m[b]是引用//此处有问题，请大佬指正
            break;
        }
    }
    for(int b=a+1;b<=n;b++)
    {
        ratio=m[b][a]/m[a][a];
        for(int c=1;c<=n+1;c++)
        {
            m[b][c]-=m[a][c]*ratio;
        }
    }
}
for(int a=n;a>=1;a--)
{
    solution[a]=m[a][n+1];
    for(int b=a+1;b<=n;b++)
    {
        solution/=m[a][a];
    }
}

举个栗子
f(x)=ax^5+bx^4+vx^3+dx^2+ex+f
可以得到f(1),f(2),f(3),f(4),f(5),f(6),然后利用高斯消元法就可以解决这个问题了

高斯消元法自动找规律机
1.打表
2.枚举次数，符合表就可以

ps:一个小技巧，读入long long的时候不知道什么系统，就这么干：

#ifdef WIN32
#define LL "%I64d"
#else
#define LL"%lld"
#endif//编译开关
long long gg;
printf(LL,gg);

day 3

动态规划

记忆化搜索

举例：数字金字塔。求一条权值最大的路径

状态：x行，y列
下一个状态：向左走，向右走

//暴力搜索法
void dfs(int x, int y, int val)
{
    val += a[x][y];
    if(x == n-1)
    {
        if(val > ans) ans = val;
        return;
    }
    dfs(x+1, y, val);
    dfs(x+1, y+1, val);
}

冗余搜索：到达同一个点时的权值比之前搜的小。
从而剪枝：利用数组F记录到达该点的权值最大值，如果搜到这儿小于F，就不继续往下搜啦。
这种通过记录状态从而减去冗余搜索的方法，叫做记忆化搜索。
在以上的例子中，记忆的是到达该点最大的权值和~

//记忆化搜索
void dfs(int x, int y, int val) 
{
    val += a[x][y];//记忆化过程
    if(val <= f[x][y]) return;
    f[x][y] = val;
    if(x == n-1) 
    {
        if(val > ans) ans = val;
        return;
    }
    dfs(x+1, y, val);
    dfs(x+1, y+1, val);
}

背包问题

例题：

Luogu 1048 : 采药
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，
他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个
难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山
洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的
价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你
是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

• 总时间：70
• 草药1 ：时间71；价值100
• 草药2 ：时间69；价值1

• 草药3 ：时间1 ；价值2

  最优选择：草药2+3：总时间70；总价值3

回忆搜索的实现：
- 状态：目前已经决定到第x件物品，当前背包中物品总重量为w，总价值为v；
- 行动：这件物品取不取；
- 约束：物品的总重量不超过W(背包总重量)；
- 目标：物品总价值最大；

冗余搜索：
当前搜索到同一件物品，且物品的总重相等时，若v1< v2,则状态1为冗余的，因为它肯定比状态2要差。
记忆化：对于每个状态(x,w)，记录对应的v的最大值。

//记忆化搜索
void dfs(int t, int x, int val) // t 为剩余时间，val 为总价值
{
    if(val <= f[t][x]) return;// 记忆化
    f[t][x] = val;
    if(x == n)
    {
        if(val > ans) ans = val;
        return;
    }
    dfs(t, x+1, val);
    if(t >= w[x]) dfs(t - w[x], x+1, val + v[x]);
}

bitset优化：

//原来写01背包的时候，循环是这么写的：
for(int i=1;i<=n;i++)
{
    for(j=m;j>=a[i];j--) if(f[j-a[i]]) f[j]=1;
}
//可以改成位运算版本的
for(int i=1;i<=n;i++)
{
    f=f|f<<a[i];
}

DP

回到数字金字塔，我们可以看到，每一步其实都走到了最大值
所以对于任意的点，它如果要到达最优值，一定是从左上方或者右上方的最大值推来的。所以利用动态规划（DP）有如下思路：
DP记录状态的最优值，并用最优值来推导出其他的最优值。
记录F[i][j] 为第i 行第j 列的路径最大值。有两种方法可以推导：
顺推：用F[i][j] 来计算F[i+1][j],F[i+1][j+1]；
逆推：用F[i-1][j],F[i-1][j-1] 来计算F[i][j]。

DP转移方程：
顺推
F[i+1][j] = MAX (F[i][j] + a[i+1][j]);
F[i+1][j+1] = MAX (F[i][j] + a[i+1][j+1]);
逆推
F[i][j] = MAX (F[i-1][j], F[i-1][j-1]) + a[i][j];//注意边界

顺推和逆推本质上是一样的；顺推和搜索的顺序类似；而逆推则是将顺序
反过来；顺推考虑的是“我这个状态的下一步去哪里”，逆推的考虑的是
“从什么状态可以到达我这里”。

//顺推
f[0][0] = a[0][0];
for(int i = 0; i < n - 1; ++ i)
    for(int j = 0; j <= i; ++ j)//分别用最优值来更新左下方和右下方
    {
        f[i+1][j] = max(f[i+1][j], f[i][j] + a[i+1][j]);
        f[i+1][j+1] = max(f[i+1][j+1], f[i][j] + a[i+1][j+1]);
    }
}

//逆推
f[0][0] = a[0][0];
for(int i = 0; i < n; ++ i)
{
    f[i][0] = f[i-1][0] + a[i][0]; //最左的位置没有左上方
    f[i][i] = f[i-1][i-1] + a[i][i]; //最右的位置没有右上方
    for(int j = 1; j < i; ++ j) //在左上方和右上方取较大的
    f[i][j] = max(f[i-1][j-1], f[i-1][j]) + a[i][j];
}
// 答案可能是最第一行的任意一列
ans = 0;
for(int i = 0; i < n; ++ i) ans = max(ans, f[n-1][i]);

还有一种思路，既然这条路一定经过最后的某个点和0,0点，那么完全可以从下往上走。权值和还是相同的w

//逆推/ 路径自底向上
//改变顺序：记录从底部向上走的路径最优值
for(int i = 0; i < n; ++ i) f[n-1][i] = a[n-1][i];
//逆推过程：可以从左下方或右下方走过来；没有边界情况
for(int i = n-2; i >= 0; -- i)
    for(int j = 0; j <= i; ++ j)
        f[i][j] = max(f[i+1][j+1], f[i+1][j]) + a[i][j];
// 答案则是顶端
ans = f[0][0];

在数字金字塔中使用DP的基础：有明确的顺序（可以划分出阶段），因此顺推逆推都可以。

动态规划(DP)：只记录状态的最优值，并用最优值来推导出其他的最优
值。

那么再看背包问题，分析一下如何使用DP
- 状态设计：记录F[i][j] 为，已经决定前i 件物品的情况，在总重量
为j 的情况下，物品总价值的最大值。同样也是有两种方法可以推导：
顺推：“我这个状态的下一步去哪里”
逆推：“从什么状态可以到达我这里”

顺推思路：对于每个状态的下一个状态，可以看为“取不取下一件物品”。
如果不取的话，可以达到状态F[i+1][j]；
如果取的话，可以达到状态F[i+1]j+w[i+1];
取上面两种状态的最大值就行了。

逆推思路：对于当前状态的上一个状态，可以看为“当前这件物品取没取”
如果没有取，那可以从F[i-1][j] 推导而来；
如果取了的话，可以从F[i-1][j-w[i]] 推导而来(需要满足重量约
束)。
同理，取上面两种状态的最大值。

采药问题的代码如下：

//DP/顺推
for(int i = 0; i < n; ++ i)
    for(int j = 0; j <= t; ++ j)
    {
        f[i+1][j] = max(f[i+1][j], f[i][j]); // 不取
        if(j + w[i] <= t)
            f[i+1][j+w[i]] = max(f[i+1][j+w[i]], f[i][j]+v[i]);// 取
    }
ans = 0;
for(int i = 0; i <= t; ++ i) ans = max(ans, f[n][i]);

//DP/逆推
for(int i = 1; i <= n; ++ i)
    for(int j = 0; j <= t; ++ j)
    {
        f[i][j] = f[i-1][j];// 不取
        if(j >= w[i]) f[i][j] = max(f[i][j], f[i-1][j-w[i]] + v[i]);// 取
    }
ans = 0;
for(int i = 0; i <= t; ++ i) ans = max(ans, f[n][i]);

可以看到，F数组是一个二维数组，使用的空间非常的大……有个奇妙的压缩空间的技巧：数组压缩（滚动数组）。
观察状态转移方程，可以发现F[i] 只由F[i-1] 决定。也就是说，前
面的很多状态对后面都是没有影响的。所以我们可以只保留前一行的状
态。

例如，F[4] 中的状态只和F[3] 中的两个状态A、B 相关

所以一个直观的做法是，记录两个数组，分别记录F[i-1] 与F[i] 的
值。
但更进一步，我们可以甚至不记录两行，只记录一行的状态。
我们倒着枚举，在F[i-1] 数组中逐步更新，让它逐步变为F[i]。

粗框中记录的是F 数组对应的值

因为是倒着枚举的，先枚举的位置都已经无用了，可以直接用F[i] 的
元素来替换。

//DP/逆推/数组压缩
// 用一个一维数组来代替二维数组
for(int i = 1; i <= n; ++ i)
    for(int j = t; j >= 0; -- j) // 重量：倒着枚举
    {
    // 不取：对数组没有影响,不用讨论了
    if(j >= w[i]) f[j] = max(f[j], f[j - w[i]] + v[i]);
    }
// 在枚举过程中，大于j 的位置等于f[i][j]，小于j 的位置等于f[i-1][j]

完全背包问题

POJ 1384 : Piggy-Bank
现在有n 种硬币, 每种硬币有特定的重量cost[i] 和它对应的价值val[i]. 每种硬币可以无限使用。已知现在一个储蓄罐中所有硬币的总重量正好为m 克, 问你这个储蓄罐中最少有多少价值的硬币? 如果不可能存在m 克的情况, 那么就输出“This is impossible.”

• 我们也把这类问题归入到背包问题当中：有物品，重量限制，价值最大。
• 但与采药问题不同的是，每件物品可以无限使用。

当前状态：F[i][j] 为，已经决定前i 件物品的情况，在总重量为j
的情况下，物品总价值的最大值。
顺推：“我这个状态的下一步去哪里”：考虑我这件物品取多少件。

如果是不取的，那可以推导到F[i+1][j]；
如果是取一件，那可以推导到F[i+1][j+w[i]]；
如果是取k 件，那可以推导到F[i+1][j+w[i]*k].

//DP/顺推
// 初值处理：由于问题求的是最小值，所以先把所有状态赋值为最大值
for(int i = 1; i <= n + 1; ++ i)
    for(int j = 0; j <= m; ++ j) f[i][j] = INF;
// 第一件还没取，重量为0
f[1][0] = 0;
for(int i = 1; i <= n; ++ i) // i：已经决定的物品
    for(int j = 0; j <= m; ++ j) // j：总重量
        for(int k = 0; j + w[i] * k <= m; ++ k) // k：这件物品取多少件
        f[i+1][j+w[i]*k] =min(f[i+1][j+w[i]*k], f[i][j] + p[i]*k );
// w 重量；p 价值

逆推：“从什么状态可以到达我这里”：考虑我这件物品取多少件。

如果是不取的，那可以从F[i-1][j] 处推导得到；
如果是取一件，那可以从F[i-1][j-w[i]] 处推导得到；
如果是取k 件，那可以从F[i-1][j-w[i]*k] 处推导得到；

// T9 / work1 : Piggy-Bank（DP/逆推）
for(int i = 0; i <= n; ++ i)
    for(int j = 0; j <= m; ++ j) g[i][j] = INF;
        g[0][0] = 0;
for(int i = 1; i <= n; ++ i)
    for(int j = 0; j <= m; ++ j)
        for(int k = 0; j >= w[i] * k; ++ k)
            g[i][j] = min( g[i][j], g[i-1][j-w[i]*k] + p[i]*k );

逆推优化：观察和逆推相关的状态。
假设w[i]=3，则F[i][6] 与F[i-1][0,3,6] 相关；F[i][7] 与
F[i-1][1,4,7] 相关；与此同时，F[i][3] 与F[i-1][0,3] 相关；
F[i][4] 与F[i-1][1,4] 相关。
则可以得到，实际上与F[i][j] 相关的状态只比F[i][j-w[i]] 多一
个。

则所以我们可以这样推导：

如果是不取的，那可以从F[i-1][j] 处推导得到；
如果是取一件或更多，那可以从F[i][j-w[i]] 处推导得到；(因为是可以
取任意件，所以从F[i] 中取最优而不是从F[i-1] 中取) 也就是，横着推……
* 而从这种逆推也可以方便的写出数组压缩。

//DP/逆推优化
for(int i = 0; i <= n; ++ i)
    for(int j = 0; j <= m; ++ j) g[i][j] = INF;
g[0][0] = 0;
for(int i = 1; i <= n; ++ i)
    for(int j = 0; j <= m; ++ j)
    {
        g[i][j] = g[i-1][j];
        if(j >= w[i]) g[i][j] = min(g[i][j], g[i][j-w[i]] + p[i]);
    }

//DP/逆推优化/数组压缩
for(int j = 0; j <= m; ++ j) f[j] = INF;
f[0] = 0;
for(int i = 1; i <= n; ++ i)
    for(int j = 0; j <= m; ++ j)
        if(j >= w[i]) f[j] = min( f[j], f[j-w[i]] + p[i] );

背包计数问题

Luogu 1466 : 集合
* 对于从1 到N (1 <= N <= 39) 的连续整数集合，能划分成两个子集
合，且保证每个集合的数字和是相等的。举个例子，如果N=3，对于
[1，2，3] 能划分成两个子集合，每个子集合的所有数字和是相等的：
- [3] 和[1,2]
* 这是唯一一种分法（交换集合位置被认为是同一种划分方案，因此不会增
加划分方案总数）如果N=7，有四种方法能划分集合[1，2，3，4，5，
6，7]，每一种分法的子集合各数字和是相等的:
- [1,6,7] 和[2,3,4,5] (注: 1+6+7=2+3+4+5)
- [2,5,7] 和[1,3,4,6]
- [3,4,7] 和[1,2,5,6]
- [1,2,4,7] 和[3,5,6]
* 给出N，你的程序应该输出划分方案总数，如果不存在这样的划分方案，
则输出0。程序不能预存结果直接输出（不能打表）。

如何引入背包模型？

• 物品：可以把所有的数字看作物品。对于数字i，其对应的重量为i，则
  我们需要求出装满载重为M 的背包的方案数(其中M 为所有数总和的一
  半)。

• 状态：（仿照之前的方法）设F[i][j] 为已经考虑完数字1-i 了，当前
  数字总和为j 的总方案数。

• 状态转移方程- 顺推：考虑有没有取数字i。
  没取：F[i+1][j] += F[i][j]
  取了：F[i+1][j+i] += F[i][j] (j+i<=M)

• 状态转移方程- 逆推：考虑有没有取数字i。
  F[i][j] = F[i-1][j] + F[i-1][j-i] (j>=i)

//DP/顺推
// 初值：（什么都不取）和=0，有一种方案
f[1][0] = 1;
for(int i = 1; i <= n; ++ i)
    for(int j = 0; j <= m; ++ j)
    {
        f[i+1][j] += f[i][j];
        if(i + j <= m) f[i+1][i+j] += f[i][j];
    }

//DP/逆推
f[0][0] = 1;
for(int i = 1; i <= n; ++ i)
    for(int j = 0; j <= m; ++ j)
    {
        f[i][j] = f[i-1][j];
        if(j >= i) f[i][j] += f[i-1][j-i];
    }

//DP/逆推/数组压缩
g[0] = 1;
for(int i = 1; i <= n; ++ i)
for(int j = m; j >= i; -- j) // 注意要倒着枚举
g[j] += g[j-i];

完全背包计数问题

Luogu 1474 : 货币系统
母牛们不但创建了它们自己的政府而且选择了建立了自己的货币系统。由于它们特殊的思考方式，它们对货币的数值感到好奇。
传统地，一个货币系统是由1,5,10,20 或25,50, 和100 的单位面值组成的。
母牛想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值。
举例来说, 使用一个货币系统[1,2,5,10,...]产生18单位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等其它。写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。

• 物品：可以把所有的货币看作物品。对于每种货币，其对应的重量为它的面值(注意到与前一道题目相比，每个物品是可以取任意件的)。
• 状态：（仿照之前的方法）设F[i][j] 为已经考虑完前i 种货币了，当前钱的总和为j 的总方案数。
• 状态转移方程- 逆推：考虑货币i 取了多少件。
  F[i][j] =ΣF[i-1][j - w[i]*k];

//DP/逆推
f[0][0] = 1;
for(int i = 1; i <= v; ++ i)
    for(int j = 0; j <= n; ++ j)
        for(int k = 0; k <= j / a[i]; ++ k)
            f[i][j] += f[i-1][j - a[i]*k];

//DP/逆推/数组压缩
g[0] = 1;
for(int i = 1; i <= v; ++ i)
for(int j = a[i]; j <= n; ++ j)
g[j] += g[j - a[i]];

总结
* 解决动态规划问题，需要注意以下几点：
- 顺序/状态：与搜索类似，依然需要考虑问题的先后顺序，以及状态的表
示
- 转移方程：有顺推与逆推两种；需要注意初值、边界情况。
* 同时在实现背包问题中，可以使用数组压缩来优化空间。

路径行走问题

Luogu 1004 : 方格取数
设有N*N 的方格图(N<=9)，我们将其中的某些方格中填入正整数，而
其他的方格中则放入数字0。
某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到
达右下角的B 点。在走过的路上，他可以取走方格中的数（取走后的方
格中将变为数字0）。
此人从A 点到B 点共走两次，试找出2 条这样的路径，使得取得的数
之和为最大。

与数字金字塔很相似。如果只走一次：
记录P[i][j]为走到第i行第j列的最大值。
但是，我们需要考虑两条道路同时进行的情况，不能单独进行。
所以我们建立一个四维数组F[i][j][k][l]来记录第一条路径走到(i,j),另一条路径走到(k,l)的最大值。对于每条路有两种可能性，2*2=4种。
注意：如果两个点同时走到同一个地方，权值只能被加一次

//DP / 逆推
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= n; ++ j)
for(int k = 1; k <= n; ++ k)
for(int l = 1; l <= n; ++ l)
{
    // 注意，如果走到了一起，只加一次
    int cost = a[i][j] + a[k][l] - a[i][j] * (i == k && j == l);//还有这种操作的说
    // 四种可能性；考虑：为什么不加边界情况的判断？
    f[i][j][k][l] = max
        (
            max(f[i-1][j][k-1][l], f[i-1][j][k][l-1]),
            max(f[i][j-1][k-1][l], f[i][j-1][k][l-1])
        ) + cost;
}

最长不下降子序列问题

Luogu 1020 : 导弹拦截
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配
备多少套这种导弹拦截系统。
389 207 155 300 299 170 158 65
最多能够拦截：6
最少要配备：2

LIS：一个序列当中一段不下降的子序列。
LDS：一个序列当中一段下降的子序列。
* 这道题目中第一问要求我们找到一段最长的单调下降的子序列。(无论是上升还是下降，可以使用类似的算法解决)
* 状态：我们用F[i] 代表，以i 位置为结尾的一段，最长的下降子序列。
* 最优性：如果某段[q1q2q3……qn]是以qn结尾的最长下降子序列；那么去掉最后一个的序列[q1q2q3……qn-􀀀1]，依然是以

F[4]从F[2]转移而来~
逆推：假设我们需要求以X 结尾的最长下降子序列F[X]；

• 由最优性可得，我们除去最后一个位置(也就是X)，还是一段最长下降子序列。
• 那我们可以枚举这个子序列的结尾Y，最优值就是F[Y]。
• 但需要注意的是，必须保证 A[ x] < A[y]，X 比Y 要低，才满足下降的
  要求。
• 我们从所有枚举的结果中找到一个最大的即可。
• 注意到题目还需要计算‘如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。’
• 可以直接观察得到，所求的答案至少为原题的最长不下降子序列。
• 因为它们当中，任意两个都不可能被同一个导弹打中。
• 事实可以证明，这就是答案。
  

图中的4 个导弹都单独需要一个系统。

//DP / LIS / 逆推
int ansf = 0, ansg = 0; // 记录所有的f(g) 中的最优值
// f 计算下降子序列，g 计算不下降子序列
for(int i = 1; i <= n; ++ i)
{
    for(int j = 1; j < i; ++ j)
        if(a[j] > a[i]) f[i] = max(f[i], f[j]);
        else g[i] = max(g[i], g[j]);
        ++ f[i], ++ g[i]; // 加上自己的一个
        ansf = max(ansf, f[i]);
        ansg = max(ansg, g[i]);
}
cout << ansf << endl << ansg << endl; // 输出答案

//P（口）S（胡）：这个代码一看就不是我的风格，空格方式完全不同，输入输出方式迥异……我从来不用流输入输出orz

Luogu 1091 : 合唱队形
N 位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1; T2; ……; TK，则他们的身高满足 T1 < ……< Ti > Ti+1 > ……> TK (1 < i < k);
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
186 186 150 200 160 130 197 220
最少需要4 位同学出列

问题转化：最少的同学出列-> 尽量多的同学留在队列

• 与LIS 的联系：如果确定了中间的“顶尖”，两侧就是“单调上升”和
  “单调下降”的。
• 容易想到枚举每个人为顶尖，分别在两端算最长下降子序列和最长上升子序列长度，加一起就是出列的人的数量。
• 状态设计：F[i] 与G[i]
• 预处理得到F[i]，G[i]
  F[i]：以i 为端点，左侧的最长的上升子序列长度。
  G[i]：以i 为端点，右侧的最长的下降子序列长度。

for(int i = 1; i <= n; ++ i) cin >> a[i], f[i] = g[i] = 1;
for(int i = 1; i <= n; ++ i)
    for(int j = 1; j < i; ++ j)
        if(a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
for(int i = n; i; -- i) // g 的计算从反方向进行枚举
    for(int j = n; j > i; -- j)
        if(a[i] > a[j]) g[i] = max(g[i], g[j] + 1);
int ans = 0;
for(int i = 1; i <= n; ++ i) // 枚举每一个顶点为顶尖
    ans = max(ans, f[i] + g[i] - 1);

最长公共子序列

Luogu 1439 : 排列LCS问题
给出1-n 的两个排列P1 和P2，求它们的最长公共子序列。
公共子序列：既是P1 的子序列，也是P2 的子序列。
3 2 1 4 5
1 2 3 4 5
最长公共子序列(LCS)：3([1 4 5])

例子中，[1 2 2 3 1] 即为序列的公共子序列

LCS：两个序列的最长公共子序列。

• 状态：我们用F[i][j] 代表，前一个序列以i 位置为结尾，后一个序
  列以j 位置为结尾，它们的最长公共子序列。

• 最优性：如果某段[q1q2q3……qn] 是分别以i，j 结尾的最长公共子序
  列；那么去掉最后一个的序列[q1q2q3……qn-􀀀1]，依然是以i-1,j-1为结尾的最长公共子序列。
  

  例子中，去掉结尾的5 后，[1 4] 仍是最长公共子序列.

• A[i] 不在公共子序列中，那么长度则等于F[i-1][j]；

• B[j] 不在公共子序列中，那么长度则等于F[i][j-1]；
• A[i] 与B[j] 都在子序列中，并且两者匹配，那么长度等于
  F[i-1][j-1]+1；
• 我们从所有枚举的结果中找到一个最大的即可。

//DP / LCS / 50 分数据规模限制
for(int i = 1; i <= n; ++ i)
    for(int j = 1; j <= n; ++ j)
    {
    // 分三种情况进行讨论
        f[i][j] = max(f[i-1][j], f[i][j-1]);
        if(p[i] == q[j]) f[i][j] = max(f[i][j], f[i-1][j-1] + 1);
    }
int ans = f[n][n];

在这道题目里，LCS问题是可以转化为LIS的：

• 假定某一个序列为[1 2 3 ... N]，那么答案则是另一个序列的LIS；
  3 2 1 4 5
  1 2 3 4 5
• 但如果两个序列都不是[1 2 3 ... N] 呢？通过转化使一个序列变成
  它，而答案不变。
  5 3 4 1 2 -> 1 2 3 4 5
  3 5 1 2 4 -> 2 1 4 5 3
  注意：原题给的序列是1-n不重复的，但是如果有重复元素，就不能这么做啦。乖乖用最长公共子序列吧……

// DP / LCS
// 初值：在遇到最小值的问题，一定要小心初值的处理
f[0][0] = 0;
for(int i = 1; i <= n; ++ i) f[i][0] = i * k;
for(int j = 1; j <= m; ++ j) f[0][j] = j * k;
for(int i = 1; i <= n; ++ i) // n 为第一个串的长度
for(int j = 1; j <= m; ++ j) // m 为第二个串的长度
{
    // 三种情况
    f[i][j] = min(f[i-1][j], f[i][j-1]) + k;
    f[i][j] = min(f[i][j], f[i-1][j-1] + abs(p[i-1] - q[j-1]));
}
int ans = f[n][m];

二维平面问题

Luogu 2733 : 家的范围
农民约翰在一片边长是N (2 <= N <= 250) 英里的正方形牧场上放牧他的奶牛。(因为一些原因，他的奶牛只在正方形的牧场上吃草。) 遗憾的是, 他的奶牛已经毁坏一些土地。( 一些1 平方英里的正方形)
* 农民约翰需要统计那些可以放牧奶牛的正方形牧场(至少是2x2的,在这些较大的正方形中没有一个点是被破坏的，也就是说，所有的点都是“1”)。
* 你的工作要在被供应的数据组里面统计所有不同的正方形放牧区域
(>=2x2) 的个数。当然，放牧区域可能是重叠。

状态设计：设状态F[i][j] 为以(i,j) 位置为右下角，最大的一个正
方形区域。
考虑位置F[i-1][j] 与F[i][j-1]；
则有F[i][j] <= F[i-1][j] + 1; F[i][j] <= F[i][j-1] + 1;

考虑* 号位置的最大区域，不可能超过4

很明显，F[i][j-1] 与F[i-1][j] 中较小值限制了最大区域的边长。

考虑* 号位置的最大区域，不可能超过3

但在某些情况下，仅考虑F[i][j-1] 与F[i-1][j] 显然不全面,还需要考虑F[i-1][j-1]。

在两个区域中，左上边界的还没有考虑入内

所以我们可以得到最终的表达式：
F[i][j] = MIN (F[i-1][j],
F[i][j-1], F[i-1][j-1]) + 1 (当(i,j) 不为障碍时)

一个正方形的大小需要考虑A,B,C 三个位置

//DP
//边界初值
for(int i = 0; i < n; ++ i) f[i][0] = (a[i][0] == '1');
for(int j = 0; j < n; ++ j) f[0][j] = (a[0][j] == '1');
for(int i = 1; i < n; ++ i)
    for(int j = 1; j < n; ++ j) if(a[i][j] == '1') // 如果是非障碍
        { // 计算
            f[i][j] = min( min(f[i-1][j], f[i][j-1]), f[i-1][j-1] ) + 1;
            t[ f[i][j] ] ++;
        }
for(int i = n; i; i --) // 统计所有方形的数目
    t[i-1] += t[i];
for(int i = 2; i <= n; ++ i) if(t[i]) // 输出结果
        cout << i << "␣" << t[i] << endl;

区间动态规划

Luogu 2734 : 游戏
有如下一个双人游戏:N(2<=N<=100)个正整数的序列放在一个游戏平台上，游戏由玩家1 开始，两人轮流从序列的任意一端取一个数，取数后该数字被去掉并累加到本玩家的得分中，当数取尽时，游戏结束。以最终得分多者为胜。
编一个执行最优策略的程序，最优策略就是使玩家在与最好的对手对弈时，能得到的在当前情况下最大的可能的总分的策略。你的程序要始终为第二位玩家执行最优策略。

如图为最优策略

状态设计方法为：F[i][j] 表示假若只用第i 个数与第j 个数之间的
数进行游戏，先手能获得的最高的分为多少。
* 我们可以根据先手取左边还是取右边来决定哪种情况得分高。
! 当先手取完一件后，先后手发生交换，而问题是类似的。

枚举区间长度(2-n)，然后按照上图方式递推。

// T19 : 游戏
cin >> n;
for(int i = 1; i <= n; ++ i)
    cin >> a[i],
s[i] = s[i-1] + a[i]; // s 代表前缀和
for(int i = 1; i <= n; ++ i) f[i][i] = a[i]; // 初值
for(int k = 2; k <= n; ++ k) // 按照序列的长度进行枚举
    for(int i = 1, j; i + k - 1 <= n; ++ i)
    {
        j = i + k - 1;
        f[i][j] = max ( // 两者取较大值
        s[j] - s[i] - f[i+1][j] + a[i],//左边总和-先手玩家得分+自己新得分=总得分
        s[j-1] - s[i-1] - f[i][j-1] + a[j]//从另一个方向
        );
    }
// 输出答案
cout << f[1][n] << "␣" << s[n] - f[1][n] << endl;

加分二叉树

Luogu 1040 : 加分二叉树
设一个n 个节点的二叉树tree 的中序遍历为（1,2,3,…,n），其中数字1,2,3,…,n 为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree 的左子树的加分× subtree 的右子树的加分＋ subtree 的根的分数。

• 若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。
  不考虑它的空子树。
• 试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要
  求输出:
  1) tree 的最高加分
  2) tree 的前序遍历

设F[i][j] 为只用第i 个数到第j 个数构成的加分树的最大权值。
枚举根节点，这样就化成了左子树和右子树的问题，求最优解即可。
状态转移方程：F[i][j] = MAX ( F[i][k-1] * F[k+1][j] + A[k] )

for(int i = 1; i <= n; ++ i) f[i][i] = a[i];
for(int i = 0; i <= n; ++ i) f[i+1][i] = 1;
for(int k = 1; k < n; ++ k)
    for(int i = 1; i + k <= n; ++ i)
    {
        int j = i + k;
        for(int l = i; l <= j; ++ l)
        f[i][j] = max(f[i][j], f[i][l-1] * f[l+1][j] + a[l]);
    }
int ans = f[1][n];

问题：如何求出树的前序遍历(树的形态)？
另外记录一个数组G[i][j]，代表F[i][j] 取最大值的时候，根节点
是什么。这样就可以通过递归来求出树的前序遍历。

for(int i = 1; i <= n; ++ i) f[i][i] = a[i], g[i][i] = i; // 边界值
for(int i = 0; i <= n; ++ i) f[i+1][i] = 1;
for(int k = 1; k < n; ++ k)
    for(int i = 1; i + k <= n; ++ i)
    {
        int j = i + k;
        for(int l = i; l <= j; ++ l)
        {
            LL t = f[i][l-1] * f[l+1][j] + a[l];
            if(t > f[i][j]) f[i][j] = t, g[i][j] = l; // 记录最优的根
        }
    }

// T25 : 加分二叉树
// 递归输出x 到y 这个树的前缀遍历
void dfs(int x, int y)
{
    if(x > y) return;
    int l = g[x][y]; // l 为根
    cout << l << "␣"; // 先输出l
    dfs(x, l-1), dfs(l+1, y); // 再输出子树的值
}
...
// 输出答案
dfs(1, n);

过程型状态划分

Luogu 1057 : 传球游戏
上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。
游戏规则是这样的：n个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师在此吹哨子时，传球停止，此时，拿着球没有传出去的那个同学就是败者，要给大家表演一个节目。
聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了m 次以后，又回到小蛮手里。两种传球方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。比如有三个同学1 号、2 号、3 号，并假设小蛮为1号，球传了3次回到小蛮手里的方式有1->2->3->1 和1->3->2->1，共2 种。

分析：这道题目十分容易用搜索解决。为什么？

• 因为题目已经明确给定了过程：传球的次数。
• 因为这个过程是一定按照顺序进行的，所以可以直接写出状态：
• 设状态F[i][j] 为传到第i 次，现在在第j 个人手上的方案数。
• 很显然F[i] 只和F[i-1] 有关；因为题目已经规定好了传递顺序。
• 这一类的过程型问题只需要找出事情发展的顺序，就可以很简单的写出状
  态与转移方程。

// T26 : 传球游戏
f[0][1] = 1; // 初值
for(int i = 1; i <= m; ++ i)
{
    f[i][1] = f[i-1][2] + f[i-1][n]; // 头与尾需要特殊处理
    f[i][n] = f[i-1][n-1] + f[i-1][1];
    for(int j = 2; j < n; ++ j) // 转移只和i-1 有关系
        f[i][j] = f[i-1][j-1] + f[i-1][j+1];
}
int ans = f[m][1];

序列型状态划分

Luogu 1018 : 乘积最大
设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1 个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。
例如，有一个数字串：312，当N=3，K=1时会有以下两种分法：
1) 3×12=36
2) 31×2=62
符合题目要求的结果是：31×2=62
现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。

题目中要求把整个序列有序地切分成K+1 个部分。

• 状态设计：设我们把前F[i][j]为前i个数字切成j部分所能得到的最大乘积。
• 很显然这时候我们只需要通过枚举最后一部分的数字有多大，就能得到结果乘积了。(满足最优性)

// T20 : 乘积最大（DP）
++ k; // K+1
f[0][0] = 1; // 初值（后面有调用）
for(int i = 1; i <= n; ++ i) // 枚举长度
for(int j = 1; j <= k; ++ j) // 枚举切割部分
for(int l = 0; l < i; ++ l) //枚举前一块的最后位置（可以为0）
f[i][j] = max(f[i][j], f[l][j-1] * val(l+1, i));
// 答案
cout << f[n][k] << endl;

为什么不枚举i,j,k？
不会需要中间一块需要被截开的情况，所以没有必要求出中间一块[i,j]的最大乘积。

Luogu 1043 : 数字游戏
丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。
游戏是这样的，在你面前有一圈整数（一共n个），你要按顺序将其分为m个部分，各部分内的数字相加，相加所得的m 个结果对10取模后再相乘，最终得到一个数k。游戏的要求是使你所得的k 最大或者最小。
例如，对于下面这圈数字（n=4，m=2）：
要求最小值时，((2-1)mod10)×((4+3)mod10)=1×7=7，要求最大值时，为((2+4+3)mod10)×(-1mod10)=9×9=81。特别值得注意的是，无论是负数还是正数，对10取模的结果均为非负值。

环形序列：第一个位置不一定是开头，有可能位于序列的中间。
解决方法：枚举每一个位置，把它当作开头算一遍，得到的结果取最大值即为答案。

复制序列一次，以每个数为开头算一次

O(n^3)

//DP
void work(int *a)
{
    s[0] = 0; // 预处理前缀和
    for(int i = 1; i <= n; ++ i) s[i] = s[i-1] + a[i];
    for(int i = 0; i <= n; ++ i)
        for(int j = 0; j <= m; ++ j)
            f[i][j] = 0, g[i][j] = INF; // 初值
            f[0][0] = g[0][0] = 1; // 初值
    ... // DP 过程

//DP
void work(int *a) //传指针
{
    ... // 初值，预处理
    for(int i = 1; i <= n; ++ i)
    for(int j = 1; j <= m; ++ j)
    for(int k = 0; k < i; ++ k)
    { // 分别计算最大值和最小值
        // 问题：为什么f 不用判断而g 需要判断
        f[i][j] = max(f[i][j], f[k][j-1] * (((s[i] - s[k]) % 10 + 10) % 10));
        if(g[k][j-1] != INF) // g[k][j-1] = INF 代表什么
            g[i][j] = min(g[i][j], g[k][j-1] * (((s[i]-s[k]) % 10 + 10) % 10));//防止为负数
}
amax = max(amax, f[n][m]);
amin = min(amin, g[n][m]);
}