DAY 5
动态规划 DP
啥是DP？
DP等价于DAG！！！
（1）无后效性：DP的所有状态之间组成一个DAG
（2）最优子序列
（3）阶段性
（4）转移方程：如何计算状态
一般是顺序转移
有时候乱序，因为DP 是DAG，可以拓扑排序，然后从头for一遍
（5）状态：题目要算的东西
以斐波那契数列为例，求斐波那契数列第n项
边界条件：
1.递推： 用其他计算好的结果得到自己的结果
2.递归：自己的值更新其他值
任何DP都可以写出这两种，但是会出现情况，一种hin难写，另一种hin简单
3.记忆化搜索
斐波那契相当于一个递归，那就写一个递归
复杂度O（数字大小，fn）
斐波那数列的第n项接近2^n
每次产生一个新数都要多次计算已经算过的项
考虑一个东西算出来就存下来
那么就记忆化搜索
int f[233];
bool g[233];
int dfs(int n)
{
if (n==0) return 0;
if (n==1) return 1;
if (g[n]) return f[n];
f[n] = dfs(n-2) + dfs(n-1);
g[n]=true;
return f[n];
}
01背包
例题：采药
N个物品，M个体积
物品i，体积vi，价值wi
头疼：设计状态
放物品，考虑有什么未知量？？？
第一维：放了多少物品，[i]放好了i个物品
第二维：体积 [j] 已经放进去的物品，体积是多少
F[i][j] 放进i个物品，体积为j的最大价值
放进物品的编号<=i ，每个物品可以放或者不放，j已经放进去i个物品的体积之和
如何转移？？？
每次都考虑好了前i种物品，那么就考虑第i+1放或者不放
如果不放第i +1个物品，体积不变，价值不变
放了后体积会+vi，价值+wi
f[ i ][ j ] = max( f[ i-1 ][ j ] , f[ i-1 ][ j-v[i] ] + wi )
外层for循环维度
状态转移
J要判断啊，不可以超过背包容积
最后答案不一定是f[n][m]，因为不一定体积越大价值越大，但是答案一定是考虑了所有n个物品，所以for一遍体积，ans取max
for (int i=1;i<=n;i++)
for (int j=0;j<=m;j++)
{
f[i][j] = f[i-1][j];
if (j >= v[i]) f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
int ans=0;
for (int a=0;a<=m;a++)
ans = max(ans,f[n][a]);
cout << ans << endl;
无限背包问题
从别人转移到自己
放0个：f[i-1][j]
放1个：f[i-1][j-vi]
放2个：f[i-1][j-2*vi]
放k个：f[i-1][j-k*vi]
可以枚举第i个物品到底放了几个
for (int i=1;i<=n;i++)
for (int j=0;j<=m;j++)
for (int k=0;k*v[i]<=j;k++)
f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
要判断k*v[i]<=j，保证体积不会爆炸
But 3层循环 O（n^3），慢了hin多
如何优化？？？
其实不需要降维，只需要把01背包改一下
f[ i ][ j ] = max( f[ i ][ j ] , f[ i ][ j-v[i] ] + w[ i ] )
之前是由i-1这种i的上一层状态转移过来的
此时就可以同一行的转移，横向转移，转移多少次就相当于一种物品放了多少个
复杂度 ： O（nm）
for (int i=1;i<=n;i++)
for (int j=0;j<=m;j++)
{
f[i][j] = f[i-1][j];
if (j >= v[i]) f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);
}
int ans=0;
for (int a=0;a<=m;a++)
ans = max(ans,f[n][a]);
cout << ans << endl;
有限背包问题
直接k枚举多少次 O（n^3）
考虑优化？？？
比如现在一个物品能放13次
造体积为vi，价值为wi，只能用1次的物品
造体积为2vi，价值为2wi，只能用1次的物品
造体积为4vi，价值为4wi，只能用1次的物品
造体积为6vi，价值为6wi，只能用1次的物品
变成捆绑包的组合
01背包问题
O（n^2 * k）
如何处理捆绑包大小？？？
相当于二进制拆分
（1）如果一个数字可以被2^k这样111111分解，那么很显然捆绑包组合起来可以实现所有值
（2）那如果不能111111这样分解，最后一定会剩下一个数字，把这个数字打包成一个捆绑包，也就是你算的时候，先算上这个数字，然后后面就变成一个可以被1111拆分的，就又回到上面情况
拆出来捆绑包个数k≈logn
所以复杂度就是O( nm logn )
只需要读入处理一下
#include<iostream>
using namespace std;
int n,m,w[233],v[233];
int f[233][233];
int main()
{
cin >> n >> m;
int cnt = 0;
for (int a=1;a<=n;a++)
{
int v_,w_,z;
cin >> v_>> w_ >> z;
int x = 1;
while (x <= z)
{
cnt ++;
v[cnt] = v_*x;
w[cnt] = w_*x;
z-=x;
x*=2;
}
if (z>0) //Z最后有剩余，新建一个捆绑包
{
cnt ++;
v[cnt] = v_*z;
w[cnt] = w_*z;
}
}
n=cnt;
for (int i=1;i<=n;i++)
for (int j=0;j<=m;j++)
{
f[i][j] = f[i-1][j];
if (j >= v[i]) f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
int ans=0;
for (int a=0;a<=m;a++)
ans = max(ans,f[n][a]);
cout << ans << endl;
return 0;
}
基础DP
希望走过的路径最大
变化量：走的过程中，位置变化
f[i][j] 走到（i,j）时走过路径的最大值
可以从左上角或者正上方转移过来
转移方程：f[ i ][ j ] = max( f[ i-1 ][ j ] , f[ i-1 ][ j-1 ] ) + a[ i ][ j ]
Joyoi
数字三角形2
PS： 实在不行加一维
f[i][j] 走到（i,j） %100 后的最大值
错误
前面的最优不一定保证后面最优
比如你现在在98 99中选择，99一定最优，但是下一步再选，就会降为hin小的数
维度不够加一维
所以考虑加一维度
bool f[i][j][k]表示走到[i][j]时的路径和%100=k是否可行
#include<iostream>
using namespace std;
bool f[233][233][233]; //bool数组
int main()
{
cin >> n;
for (int i=1;i<=n;i++)
for (int j=1;j<=i;j++)
cin >> a[i][j];
f[1][1][a[1][1] % 100] = true; //初始化
for (int i=1;i<n;i++)
for (int j=1;j<=i;j++)
for (int k=0;k<100;k++)
if (f[i][j][k]) //判断之前是否可达，否则走就没必要
{
f[i+1][j][(k+a[i+1][j])%100]=true;
f[i+1][j+1][(k+a[i+1][j+1])%100]=true;
}
for (int j=1;j<=n;j++) //最后枚举在哪一列
for (int k=0;k<100;k++)
if (f[n][j][k]) ans=max(ans,k);
cout << ans << endl;
return 0;
}
最长上升子序列（数据结构优化）
f[i] 以i为结尾的最长上升子序列的长度
O（n^2）
N<=1e5 --->线段树
状压DP
- 平面上N个点，第i个点坐标（xi,yi），从1号点出发，在平面上任意走，求走遍所有点再回来的最短路径
使得距离最短，一个点没必要走两次，每次从没走过的点选一个出来
f[s][i] i 在i点，s走过了哪些点
状态压缩：把一个数组压缩成一个数
自己更新别人
所以我们要找没走过的点，枚举j，看看s的第j位二进制位是不是0
最后答案看看停在那个点，最后还要回来
#include<iostream>
using namespace std;
double f[][];
double x[233],y[233];
int main()
{
cin >> n;
for (int a=0;a<n;a++)
cin >> x[a] >> y[a];
f=∞
f[1][0]=0;
for (int s=0;s<(1<<n);s++)
for (int i=0;i<n;i++)
if (f[s][i] < ∞)
{
for (int j=0;j<n;j++)
if ( ((s>>j) & 1) == 0)
{
int news = s | (1<<j);
f[news][j] = min(f[news][j],f[s][i] + dis(i,j));
}
}
for (int i=0;i<n;i++)
ans=min(ans, f[(1<<n)-1][i] + dis(i,0));
return 0;
}
O(2^n * n^2)
N<=22或者N<=20
一定是先枚举s，然后s从小到大，因为走过的点是越来越多的
旅行商问题 TSP问题
一个点四联通不种草
F[i][s] 前i行已经种完了，而且第i行草种成了什么样，二进制数代表第i行每个位置中不中草
此情况下的方案数
i+1行的S’二进制没有相邻的1
第i行的草和i+1行的草不相邻
S&S’=0 上下没有相邻的草
这个题恰好放k个国王，多了一个条件，多加一个维度
f[i][s][j] 前i行国王已经放好了，已经放了j个国王，s记录第i行国王摆放状态
数位DP
按照数的每一位数字一位一位转移
给定两个数L~R ,求有多少个数
(1)前缀和转化
0~R– 0~L-1
问题转化0~x中有多少个数
千 百 十 个
3 2 4 5
求多少个y,满足0<=y<=x
满足条件的y最多4 位，一位一位填数
从高位向低位填数
f[i][j] 已经填到了i位，j=0填的数已经小于x，j=1填的数不确定是否小于x,目前填的数字和x一样，在这种情况下有多少个数
转移，下一位填0~9中的哪个数
数组z存x的每一位
X只有L位，填到L+1位和x相等的方案数为1 ，都填 0
自己更新别人
J枚举小于还是等于
考虑填k之后y会不会比x大
#include<iostream>
using namespace std;
int solve(int x)
{
int l=0;
while (x>0)
{
l++;
z[l] = x%10;
x/=10;
}
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
f[l+1][1]=1;
g[l+1][1]=0;
for (int i=l+1;i>=2;i--)
for (int j=0;j<=1;j++)
for (int k=0;k<=9;k++)
{
if (j==1 && k>z[i-1]) continue;
int j_;
if (j==0) j_=0;
else if (k==z[i-1]) j_=1;
else j_=0;
f[i-1][j_] += f[i][j];
g[i-1][j_] += f[i][j] * k + g[i][j];
}
return g[1][0] + g[1][1];
}
int main()
{
cin >> l >> r;
cout << solve(r) - solve(l-1) << endl;
return 0;
}
多一个条件多一个维度
F[i][j][k] 填好了前i位
保证相邻两位>0
F[i][j][k] k存当前乘积的话，太大存不下
多加维度
r都是1位数相乘，>10的质因子不可能出现，所以r当中有hin多空位置
分解质因数
数组里面有hin多空的
那就分解开
因为还是会有浪费，因为这些质数不可能同时达到上界
BFS预处理算出30000多个长成这个样子的数字 f[i][j][k] 直接用就好
树形DP
给你一棵N个点的树，让你求有多少个点
树形DP必须是有根数，没有根就加根
f[i] 以i为根的子树有多少个点
树形DP转移：儿子节点整合转移到父亲节点
在树上找到两个点，使得他们的距离最远
A->LCA->B
看做LCA向下的两段
F[i][0] 从i点向下的最大路径长
F[i][1] 从i点向下的次大路径长
F[i][0]=max( f[pj][0] ) + 1
假设最长路经过pk
F[i][1] 在剩下点里面找最长路，不找 pk了
#include<iostream>
using namespace std;
void dfs(int i)
{
for (p is i's son)
dfs(p); //由于所有点都是从下面转过来的，所以先递归儿子
for (p is i's son)
{
int v = f[p][0]+1;
if (v>f[i][0]) //找到一条新的最长路
{
f[i][1]=f[i][0];
f[i][0]=v;
}
else if (v>f[i][1]) f[i][1]=v;
} //否则和次长路比较
}
int main()
{
cin >> n;
du ru he jian shu;
dfs(1);
return 0;
}
P3304 [SDOI2013]直径
P4408 [NOI2003]逃学的小孩
所有点之间路径的长度之和（边权都是1）
F[i] 以i为根的子树有多少个点
枚举两个点，找他们的路径
转化：
考虑一条边可以被多少条路径被经过
第一个点在子树里，子树外
f[i] 以i为根的子树，所得边权之和最大
f[i][0 / 1] 在以i为根的子树里，0à i没选，1ài选了
i选了，那么他的儿子都不能选
f[i][j]=∑ f[j][0] + a[i] (j shuyi son[i])
i不选，他的儿子可以选或者不选
f[i][0/1] i的子树都被守护，i放不放士兵
和上一个题几乎一样
变式：
每个士兵都会守护距离自己不超过2的节点
f[i][0/1/2] i的子树被完全覆盖，从i向下走，距离最近的士兵的距离是0/1/2
0à自己是兵
1à儿子是兵
2à孙子是兵
g[j][0/1]
确定了前j个儿子的取值，其中有没有一个儿子用自己的0值更新答案（有没有一个儿子上边有士兵）再来一个DP
DP套DP
N堆石子，a1,a2,a3,a4,...可以合并任意两堆石子，合并代价为两堆石子的异或 ^ 和，求最小代价，N<=16
状压DP
f[s] 把s堆石子合并成一堆得最小代价，那么ans= f [ 2^n - 1 ]
最后一次操作也是吧两边石子合成一堆
S现在包含 5 3 2 0堆石子
你现在会有以下的情况：
枚举s的所有子集，然后和剩下的合并
then
枚举子集，子集所对应的数一定比s小，可以直接枚举一个a，比s小（从1枚举，0无意义）
复杂度（2^n * 2^n = 4^n）
优化？？？
能不能只去枚举s的子集，那么会变快
模拟一下看看它在干哈
复杂度（3^n）
3^n n=16，14 的状压
#include<iostream>
using namespace std;
int main()
{
cin >> n;
for (int a=0;a<n;a++)
cin >> z[a];
for (int a=0;a<(1<<n);a++)
for (int b=0;b<n;b++)
if (a & (1<<b))
sum[a] += z[b]; //a状态石子的总个数
memset(f,0x3f,sizeof(f)); //求最小值，初始化无穷大
for (int a=0;a<n;a++)
f[1<<a] = 0; //把一堆石子合并，代价为0
//未优化
/*
for (int s=0;s<(1<<n);s++)
for (int a=1;a<s;a++) //枚举s的子集
if ( (s|a) == s) //判断是不是s的子集
f[s] = min(f[s],f[a]+f[a^s]+(sum[a]^sum[a^s]));
*/
//优化后
for (int s=0;s<(1<<n);s++)
for (int a=(s-1)&s;a;a=(a-1)&s) //仅枚举s的子集，把a变成s的子集
f[s] = min(f[s],f[a]+f[a^s]+(sum[a]^sum[a^s]));
cout << f[(1<<n)-1] << endl;
}
博弈论DP
1. 一个游戏G，两个人玩，Alice 和 Bob
2.回合制游戏：a,b,a,b,a,b.......
3.游戏没有平局
4.胜负的区分方法：当某个人无法继续操作，他就输了，所以不存在计分
两人玩游戏，回合制，谁减到0谁就赢
一般问的问题是，先手是否必胜/败
so,如何Dp？？？
游戏G有hin多状态，每进行一次操作，当前状态变成另一个状态，当没有状态可以转移，就必败
必败态：谁在这个状态操作，谁必败
必胜态：在此操作，对面进入必败态
DP DAG，拓扑处理
如果从一个点出发，走一步能够走到必败态，他就是必胜态
f[s] s是游戏的一个状态，f代表这个状态是必胜还是必败
如果存在si是false，那么他就是必胜态
回题目：
未知量：还剩下多少数字，上一次对手减去的数字
f[i][j] 数字还剩下 i，对手上一轮减的数字是 j，此时自己是必胜态还是必败态
枚举1<=r<=k*j
那么f[i][j] 可以转移到 f[i-r][r]
博弈论DP建议记忆化搜索
ALice第一步可以减去1~s-1的所有数字，一旦她可以转移到一个对手的必败态，那么她一定必胜
DFS终止条件 i=0 ，自己就输了 ，还剩下0，就说明上一轮对手已经把数字减到0了
f 必胜必败态记录，g记录是否被算过
#include<iostream>
using namespace std;
bool f[][],g[][];
//g[][]记忆化搜索，记录是否搜索过
bool dfs(int i,int j)
{
if (i==0) return false;
if (g[i][j]) return f[i][j];
g[i][j]=true;f[i][j]=false;
for (int r=1;r<=i && r<=k*j;r++)
if (dfs(i-r,r) == false) f[i][j]=true;
return f[i][j];
}
int main()
{
cin >> s >> k;
for (int a=1;a<s;a++) //枚举Alice的转移状态
if (dfs(s-a,a) == false) //一旦她可以转移到一个必败态，那她一定是必胜态
{
cout << "Alice" << endl;
return 0;
}
cout << "Bob" << endl;
return 0;
}
Type 2
两个人A,B，回合制，不能动为输
一共N个游戏，每次Alice和Bob可以从中挑一个游戏玩
取石子游戏
N堆石子，a1,a2,a3.....an
A,B每次可以从某一堆石子中取走任意多个石子。当谁没有办法再取石子，就输了
N维DP？？？
sg[0]=0 对于任何必败态的值为0
sg[1]= .... 找到1能转移到的所有状态的sg值，写出来，从中找一个最小的没有出现的自然数
..........
sg[n]
对于本题目，sg没有必要刻意算
再看一下SG
SG函数有啥用？？？
如果一个游戏的SG！=0 先手必胜
SG==0 先手必败
如何变成N个游戏？？？
SG定理：
N个游戏的sg值等于每个游戏的sg值异或起来
证明正确性，自行百度（然后你看了不到20'就会放弃）
int main()
{
cin >> n;
int ans=0;
for (int a=1;a<=n;a++)
{
int v;
cin >> v;
ans = ans ^v;
}
if (ans!=0) cout << "Alice" << endl;
else cout << "Bob" << endl;
}
P2197 【模板】nim游戏
变式
N堆石子,a1,a2,a3,.....an
每次可以从一堆石子中取走1~4个石子
PS：一般与sg函数有关的题，都是要找规律，手算SG值，写到程序里
sg[0]=0
sg[1]=1
sg[2]=2
sg[3]=3
sg[4]=4
sg[5]=0
sg[6]=1
.................
sg[ai]=ai%5
所以算每个数%5的异或和，非0 ，先手必胜，否则先手必败
（20多道博弈论题目）
把问题转化为基本取石子游戏 nim
算出每堆得奇偶性
把所有奇数堆的下标取出来，然后异或下标，等于0 ，先手必败，否则必胜
操作有两种情况：
（1）左偶右奇
相当于把1从右向左移
（2）左奇右奇
有两堆一样的东西，相当于没有，因为异或起来为0
所以就是把1不断往前移动，直到把1移到第一堆就无路可走了，因为此时就是只有第一堆是1 ，其余都是0，没法选啊
因为这道题下标数就是这堆石子数
每次向前移动1,下标减小，相当于石子数减小这样任意 i < j, 就可以把 j取成 j - 1, j - 2, j - 3 到 0，然后原题就变成那个简单题了
就是说如果是奇数，我把奇数的那堆移到最左边就好了，如果是偶数，还是向左取，因为这样也是最优操作
把所有下标为奇数的石子数目异或
只要对手能把偶数搬到奇数位置，奇数都能被搬去偶数位置
任何石子被搬到偶数位上都没用，不影响局面
搬奇数的就好
同上一个题
只有距离终点的曼哈顿距离为奇数的格子上的棋子对于题目有用
每个人的标记都是一样的
f[s] 在s状态下，哪个位置有没有标记过，此情况下必胜或者必败，但是存不下
考虑当做多个游戏
sg[i] 对于一个长度为i的横条,是必败态还是必胜态
所以本题就是sg[3]^sg[4]
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int dfs(int n)
{
if (n==0) return 0;
if (f[n]) return sg[n];
f[n]=true;
vector<int> z; //记录能够转移到的所有sg值
for (int a=1;a<=n;a++) //枚举中间可用点，把游戏拆成两份
{
int l = max(a-3,0); //看左右两边可用长度
int r = max(n-a-2,0);
z.push_back( dfs(l) ^ dfs(r) ); //求出当前点能够转移到的所有状态的sg值
}
sort(z.begin(),z.end()); //先排序
z.push_back(233333333);
//在数组后面放一个hin大的数字，防止越界，因为sg可能大于数组中的任何一个数
//求sg值
for (int a=0,p=0;;a++)
{
if (z[p] != a)
{
sg[n] = a;
return sg[n];
}
while (z[p]==a) //sg值可能有重复
p++;
}
}
int main()
{
cin >> n;
if (dfs(n)) cout << "Alice" << endl;
else cout << "Bob" << endl;
}
f[x][y] 当前状态为（x,y）时，是必胜态还是必败态
注意题目n<=30000
发现存不下
优化：拆分
x=2^a*3^b
P3541 [POI2012]LIC-Bidding
强烈安利
acm.gdu.edu.cn
ACM Steps 有hin多专题训练