qbzt day5 上午

动态规划

递推递归记忆化搜索

斐波那契数列

1、用其他已经计算好的结果计算自己的结果（递推）

2、用自己的值计算别人的值（考虑对之后的项做出的贡献）

cin >> n;

    f[]=;f[]=;

    for (int a=;a<=n;a++)

        f[a] = f[a-] + f[a-];

    for (int a=;a<n;a++)

    {

        f[a+] += f[a];

        f[a+] += f[a];

    }

理论上两种方法都是可以的，但有的题一种方法会很难写，另一种方法就很好写，所以两种都需要掌握

3、记忆化搜索

递归处理斐波那契数列的第n项，找到边界，遇到第一项返回1，遇到第2项返回0。

这样的话复杂度是O(f[n])的，因为他是由一个一个1累加起来的

接近(2^n)

慢的原因是我们把很多项重复算了很多次

我们考虑把已经算出来的项存下来，之后直接调用就行了

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];

}

无后效性：动态规划的所有状态之间组成了一个有向无环图

如果出现乱序转移的情况，就考虑拓扑排序（把所有的边变成从前往后），之后for一遍就行了

阶段性：

转移方程：怎么算

状态：要算的东西

背包

P1 N个物品，M的容积，每个物品有体积和价值，最大化价值和

采药

第一个维度：现在放了多少个物品，第二个维度：用了多少体积

设f[i][j]表示已经试到了第i个物品（第i个物品之前的都有可能放或者不放，但是编号都小于等于i），已经放进去的体积之和为j 这种情况下所取得的最大价值

那么第i+1个物品有两种情况：放或者不放

如果不放，f[i+1][j]=f[i][j]

如果放，f[i+1][j+v[i+1]]=f[i][j]+w[i+1]

这个方程是自己更新别人

如果用别人更新自己

不放：f[i][j]=f[i-1][j]

放：f[i][j]=f[i-1][j-v[i]]+w[i]

直接取max

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

int f[][];

int main()

{

    cin >> n >> m;

    for (int a=;a<=n;a++)

        cin >> v[a] >> w[a];

    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 ;

}

记得加判断，最后要在所有的体积的价值中取max

P2 每个物品可以用无限次

枚举第i个物品到底放了多少个

直接枚举复杂度会炸掉

其实这个时候直接从自己转移过来就行了

f[i][j]=f[i-1][j-v[i]]+w[i]把i-1换成i，相当于是枚举了，但是复杂度会降下来O(nm)

#include<iostream>

using namespace std;

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

int f[][];

int main()

{

    cin >> n >> m;

    for (int a=;a<=n;a++)

        cin >> v[a] >> w[a];

    /*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]);*/

    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 ;

}

P3 有限背包每个物品可以用无限次

直接枚举第i个物品用多少次

复杂度将近O(n^3)

如何优化？

直接造物品

比如有一个可以用13次，体积为v[i]的物品

我们把它分成只可以用一次的体积为v[i],2v[i],4v[i],6v[i]的物品，那么这和原问题是等价的

问题就变成了0/1背包

复杂度O(nmk)(k表示分成了多少个小的捆绑包)

怎么分呢？

先按照二进制从小到大一个一个拆，直到不足够下一个二进制了就把剩下的单独拆出来

比如11=2^0+2^1+2^2+6

K≈log(n)

复杂度也就是O(nmlogn)

证明：比如31=2^0+2^1+2^2+2^3+2^4

37=31+6

就ok了

#include<iostream>

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>)

        {

            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

例数字三角形

每个位置可以由上方或者左上方得到

f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j]

数字三角形2

我们发现前面的和模100时大，但是后面不一定大

考虑加一维

定义bool数组f[i][j][k]表示走到[i][j]时模100为k是否可能

转移方程：f[i][j][k]=f[i-1][j-1][(k-a[i][j])%100]||f[i-1][j][(k-a[i][j])%100]
边界f[1][1][a[1][1]%100]=true
然后找到一个最大的k

转移的时候用自己的值更新其他的值就可以了

dp要注意加维度

#include<iostream>

using namespace std;

bool f[][][];

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]=max(f[j])(1<=j<i)+1

复杂度O(n^2)

当数据范围10^5时就线段树或者平衡树维护一下就行了

dp有的时候可以用数据结构优化

区间dp

例：合并石子

我们发现合并的话一定是把相邻的区间合并成一堆石子

比如把1和4合并，2和3肯定已经被合并过了

满足只能合并相邻的两个东西，这样的一定是区间dp

状态：f[l][r]表示把第l堆石子和第r堆石子合并的最小代价是多少

考虑在a[l]到a[r]之间找到一条分界线，先把左边的合并，再把右边的合并，再把这两堆合并

f[l][r]=min(f[l][p]+f[p+1][r])+sum[r]-sum[l-1] (l<=p<r)

最后求得答案就是f[1][n]

最直观的想法：枚举l，r，p

但是这样是不对的

比如枚举[1,n]中的p=2，我们发现f[3][n]还没有算出来，那就gg了

所以我们应该第一维枚举长度，第二维枚举左右端点，第三维枚举端点就好了

for (int a=;a<=n;a++)

    {

        cin >> z[a];

        sum[a] = sum[a-]+z[a];

    }

    memset(f,0x3f,sizeof(f));

    for (int a=;a<=n;a++)

        f[a][a] = ;

    for (int len=;len<=n;len++)

        for (int l=,r=len;r<=n;l++,r++)

            for (int p=l;p<r;p++)

                f[l][r] = min(f[l][r],f[l][p]+f[p+][r]+sum[r]-sum[l-]);

    cout << f[][n] << endl;

矩阵乘法，调整运算次序使得运算次数最小

最后是把n个矩阵合并成1个矩阵

每次合并相邻两个矩阵

f[l][r]表示把l~r的矩阵合并成一个矩阵所需要的最小次数

还是枚举断点

f[l][r]=min(f[l][p]+f[p+1][r])+a[l]*a[p+1]*a[r+1] (l<=p<r)

按照石子合并的方式搞一搞就行了

状压dp

平面上有n个点，第i个点的坐标为(x[i],y[i])。有一个人刚开始在一号点，想让他走完其他的点再回到原点，问你最短的距离是多少

变化量：我现在在哪个点，我已经走过了哪些点

f[s][i]表示我走过了哪些点，现在在第i个点

状态压缩：把一个数组压缩成一个数。

哪个点经过了就把他对应的二进制的位数变成1

转移：枚举j，当二进制位第j位为0时就可以考虑转移

除了f[1][0]=0，其他初始化为1

Dp完之后再循环一遍找答案

要先枚举s在

复杂度O(2^n * n^2)

一般来说状压dp解决的范围在n<=22或n<=20

double f[][];

double x[],y[];

int main()

{

    cin >> n;

    for (int a=;a<n;a++)

        cin >> x[a] >> y[a];

    f=∞

    f[][]=;

    for (int s=;s<(<<n);s++)

        for (int i=;i<n;i++)

            if (f[s][i] < ∞)

            {

                for (int j=;j<n;j++)

                    if ( ((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 ;

}

巴特西

qbzt day5 上午

最新文章

热门文章