DAY 5 & 6
阅读原文时间:2023年07月15日阅读:2

DAY 5

之前整过一个DP

动态规划  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[];
bool g[];

int dfs(int n)
{
if (n==) return ;
if (n==) return ;
if (g[n]) return f[n];
f[n] = dfs(n-) + dfs(n-);
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=;i<=n;i++)  
    for (int j=;j<=m;j++)  
    {  
        f\[i\]\[j\] = f\[i-\]\[j\];  
        if (j >= v\[i\]) f\[i\]\[j\] = max(f\[i\]\[j\],f\[i-\]\[j-v\[i\]\]+w\[i\]);  
    }

int ans=;  
for (int a=;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=;i<=n;i++)
for (int j=;j<=m;j++)
for (int k=;k*v[i]<=j;k++)
f[i][j] = max(f[i][j],f[i-][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=;i<=n;i++) for (int j=;j<=m;j++) { f[i][j] = f[i-][j]; if (j >= v[i]) f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);
}
int ans=;
for (int a=;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拆分的,就又回到上面情况

比如:10101

1111可以表示1~1111的所有数字

剩下110

1~1111都加上110

就可以表示111~10101

所以就可以表示1~10101

拆出来捆绑包个数k≈logn

所以复杂度就是O( nm logn )

只需要读入处理一下

#include

using namespace std;

int n,m,w[],v[];
int f[][];

int main()
{
cin >> n >> m;
int cnt = ;
for (int a=;a<=n;a++) { int v_,w_,z; cin >> v_>> w_ >> z;

    int x = ;  
    while (x <= z)  
    {  
        cnt ++;  
        v\[cnt\] = v\_\*x;  
        w\[cnt\] = w\_\*x;  
        z-=x;  
        x\*=;  
    }  
    if (z>)  //Z最后有剩余,新建一个捆绑包  
    {  
        cnt ++;  
        v\[cnt\] = v\_\*z;  
        w\[cnt\] = w\_\*z;  
    }  
}  
n=cnt;  
for (int i=;i<=n;i++)  
    for (int j=;j<=m;j++)  
    {  
        f\[i\]\[j\] = f\[i-\]\[j\];  
        if (j >= v\[i\]) f\[i\]\[j\] = max(f\[i\]\[j\],f\[i-\]\[j-v\[i\]\]+w\[i\]);  
    }  
int ans=;  
for (int a=;a<=m;a++)  
    ans = max(ans,f\[n\]\[a\]);  
cout << ans << endl;  
return ;  

}

基础DP

DP----鬼畜的数字三角形

希望走过的路径最大

变化量:走的过程中,位置变化

f[i][j] 走到(i,j)时走过路径的最大值

可以从左上角或者正上方转移过来

转移方程:f[ i ][ j ] = max( f[ i-1 ][ j ] , f[ i-1 ][ j-1 ] ) + a[ i ][ j ]

Joyoi

http://www.joyoi.cn/

数字三角形2

PS: 实在不行加一维

f[i][j] 走到(i,j) %100 后的最大值

错误

前面的最优不一定保证后面最优

比如你现在在98 99中选择,99一定最优,但是下一步再选,就会降为hin小的数

维度不够加一维

所以考虑加一维度

bool  f[i][j][k]表示走到[i][j]时的路径和%100=k是否可行

#include

using namespace std;

bool f[][][]; //bool数组

int main()
{
cin >> n;
for (int i=;i<=n;i++) for (int j=;j<=i;j++) cin >> a[i][j];

f\[\]\[\]\[a\[\]\[\] % \] = true;  //初始化  
for (int i=;i<n;i++)  
    for (int j=;j<=i;j++)  
        for (int k=;k<;k++)  
            if (f\[i\]\[j\]\[k\])  //判断之前是否可达,否则走就没必要  
            {  
                f\[i+\]\[j\]\[(k+a\[i+\]\[j\])%\]=true;  
                f\[i+\]\[j+\]\[(k+a\[i+\]\[j+\])%\]=true;  
            }

for (int j=;j<=n;j++)   //最后枚举在哪一列  
    for (int k=;k<;k++)  
        if (f\[n\]\[j\]\[k\]) ans=max(ans,k);  
cout << ans << endl;

return ;  

}

最长上升子序列

数据大的话就数据结构优化

f[i] 以i为结尾的最长上升子序列的长度

O(n^2)

N<=1e5   --->线段树

区间DP

状压DP

  1. 平面上N个点,第i个点坐标(xi,yi),从1号点出发,在平面上任意走,求走遍所有点再回来的最短路径

使得距离最短,一个点没必要走两次,每次从没走过的点选一个出来

f[s][i]  i 在i点,s走过了哪些点

状态压缩:把一个数组压缩成一个数

自己更新别人

所以我们要找没走过的点,枚举j,看看s的第j位二进制位是不是0

最后答案看看停在那个点,最后还要回来

#include

using namespace std;

double f[][];
double x[],y[];

int main()
{
cin >> n;
for (int a=;a> x[a] >> y[a];
f=∞
f[][]=;
for (int s=;s<(<>j) & ) == )
{
int news = s | (<<j);
f[news][j] = min(f[news][j],f[s][i] + dis(i,j));
}
}
for (int i=;i<n;i++)
ans=min(ans, f[(<<n)-][i] + dis(i,));

return ;  

}

O(2^n  *  n^2)

N<=22或者N<=20

一定是先枚举s,然后s从小到大,因为走过的点是越来越多的

旅行商问题 TSP问题

P1171 售货员的难题

P1879 [USACO06NOV]玉米田

一个点四联通不种草

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行国王摆放状态

P1896 [SCOI2005]互不侵犯

数位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

using namespace std;

int solve(int x)
{
int l=;
while (x>)
{
l++;
z[l] = x%;
x/=;
}
memset(f,,sizeof(f));
memset(g,,sizeof(g));
f[l+][]=;
g[l+][]=;
for (int i=l+;i>=;i--)
for (int j=;j<=;j++) for (int k=;k<=;k++) { if (j== && k>z[i-]) continue;
int j_;
if (j==) j_=;
else if (k==z[i-]) j_=;
else j_=;
f[i-][j_] += f[i][j];
g[i-][j_] += f[i][j] * k + g[i][j];
}
return g[][] + g[][];
}

int main()
{
cin >> l >> r;
cout << solve(r) - solve(l-) << endl;

return ;  

}

多一个条件多一个维度

F[i][j][k] 填好了前i位

保证相邻两位>0

P2657 [SCOI2009]windy

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

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\]\[\]+;  
    if (v>f\[i\]\[\]) //找到一条新的最长路  
    {  
        f\[i\]\[\]=f\[i\]\[\];  
        f\[i\]\[\]=v;  
    }  
    else if (v>f\[i\]\[\]) f\[i\]\[\]=v;  
}   //否则和次长路比较  

}

int main()
{
cin >> n;
du ru he jian shu;

dfs();

return ;  

}

P3304 [SDOI2013]直径

P4408 [NOI2003]逃学的小孩

所有点之间路径的长度之和(边权都是1)

F[i] 以i为根的子树有多少个点

枚举两个点,找他们的路径

转化:

考虑一条边可以被多少条路径被经过

第一个点在子树里,子树外

P1352 没有上司的舞会

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不选,他的儿子可以选或者不选

P2016 战略游戏

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

P2279 [HNOI2003]消防局的设立

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

using namespace std;

int main()
{
cin >> n;
for (int a=;a> z[a];
for (int a=;a<(<<n);a++)
for (int b=;b<n;b++)
if (a & (<<b))
sum[a] += z[b]; //a状态石子的总个数

memset(f,0x3f,sizeof(f)); //求最小值,初始化无穷大  
for (int a=;a<n;a++)  
    f\[<<a\] = ;  //把一堆石子合并,代价为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=;s<(<<n);s++)  
    for (int a=(s-)&s;a;a=(a-)&s) //仅枚举s的子集,把a变成s的子集  
        f\[s\] = min(f\[s\],f\[a\]+f\[a^s\]+(sum\[a\]^sum\[a^s\]));

cout << f\[(<<n)-\] << 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

using namespace std;

bool f[][],g[][];
//g[][]记忆化搜索,记录是否搜索过
bool dfs(int i,int j)
{
if (i==) return false;
if (g[i][j]) return f[i][j];
g[i][j]=true;f[i][j]=false;
for (int r=;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=;a<s;a++) //枚举Alice的转移状态
if (dfs(s-a,a) == false) //一旦她可以转移到一个必败态,那她一定是必胜态
{
cout << "Alice" << endl;
return ;
}
cout << "Bob" << endl;

return ;  

}

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=;
for (int a=;a<=n;a++) { int v; cin >> v;
ans = ans ^v;
}
if (ans!=) 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
#include
#include

using namespace std;

int dfs(int n)
{
if (n==) return ;
if (f[n]) return sg[n];
f[n]=true;
vector z; //记录能够转移到的所有sg值
for (int a=;a<=n;a++) //枚举中间可用点,把游戏拆成两份
{
int l = max(a-,); //看左右两边可用长度
int r = max(n-a-,);
z.push_back( dfs(l) ^ dfs(r) ); //求出当前点能够转移到的所有状态的sg值
}

sort(z.begin(),z.end());  //先排序  
z.push\_back();  
//在数组后面放一个hin大的数字,防止越界,因为sg可能大于数组中的任何一个数

//求sg值  
for (int a=,p=;;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多专题训练

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章