清北学堂提高组突破营游记day5

时间:2022-07-12 09:50:22

 

长者zhx来啦。。

又要送冰红茶了。。。

zhx一上来就讲动态规划。。。是不是要逼死人。。。。

动态规划:

最简单的例子:斐波那契数列。因为他是递推(通项公式不算)的,所以前面的已经确定的项不会影响后面的,满足无后效性,为最简单的动态规划。

3种写法:用算好的自己来算别人,或者用别人更新自己,记忆化搜索。

计算斐波那契数列f[n]=f[n-1]+f[n-2]。

如果用dfs来计算的话,在dfs函数里return dfs(n-1)+dfs(n-2);

由于没有记忆化,(没有把每一个阶段记录下来,)复杂度达到了f[n]级别而线性地推可以O(n)。

这就是为什么记忆化。

 

(zhx:我课件只有130页,没什么东西。。

动态规划过程图

画成图就是dag有向无环图。

背包问题:洛谷p1048采药。

代码:

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 3404;
const int maxm = 12882;
int main()
{
    int N,W;
    int w[maxn],v[maxn],value[101][1001];
    cin>>W>>N;
    for(int i=1;i<=N;i++)
        cin>>w[i]>>v[i];
    memset(value,0,sizeof(value));  //value数组注意要清空
    
    for(int i=1;i<=N;i++)  
        for(int j=W;j>=0;j--)
        {
            if(j>=w[i])
               value[i][j]=max(value[i-1][j],value[i-1][j-w[i]]+v[i]);
            else value[i][j]=value[i-1][j];
        }
    
    cout<<value[N][W]<<endl;  
    return 0;}

然后是无限背包,有限背包。

然后是区间dp,

例题为合并石子

满足只能合并相邻的两个元素的题为区间dp。

代码:

状压dp:洛谷p1171

如果一个题数据n<=20||22,考虑状压dp。

洛谷p1879玉米田,状压dp;

P1896 [SCOI2005]互不侵犯,状压dp;

然后是数位dp:

P2657 [SCOI2009]windy数

树形dp:

题目:对于一棵有n个点的树,求它有多少个点。

(题目无锅)。

要求用树形dp做。

原理:处理子树。我们设f[i]表示i节点以及他的子树一共有多少个节点。那么转移方程为f[i]=Σf[j](子树)+1(自己);

最后输出f[1];

 

博弈论dp:  明天再讲。