首页 > 其他分享 >动态规划 1

动态规划 1

时间：2023-01-25 21:34:14浏览次数：66  
标签：read ll i2 j2 while 动态 规划 getchar

01背包

模板题（AcWing.2）

题目描述

有 \(n\) 件物品和一个容量是 \(V\) 的背包。每件物品只能使用一次。
第 \(i\) 件物品的体积是 \(vi\)，价值是 \(wi\)。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

样例

in：

4 5
1 2
2 4
3 4
4 5
111

out：

```cpp
8

思路：

image

  1. 表示状态

    设f[i][j]表示只考虑前 \(i\) 个物品，总共体积不大于 \(j\) 时的最大价值。

  2. 循环范围

    \(i\) 表示物品数量，物品最少 1 个，物品最多 \(n\) 个，因此 \(i\) 的循环范围是 1~\(n\) 。
    \(j\) 表示总共体积，体积最小是 0 ，体积最大是 \(V\) ，因此 \(j\) 的循环范围是 0~\(V\) 。

  3. 状态转移

    由于每个状态是由前一个状态推来的，所以要决定当前物品是选还是不选。
    如果选这个物品不优，那么就不选它，所以每个状态一定不会比之前的任何一个状态更差。
    然后可以得出：

    如果不选当前物品，则价值为f[i-1][j]

    如果选当前物品：
    要给这个物品在 \(j\) 个单位的空间中腾出位置，还得保证留下的物品时最优的。
    留下的物品的总价值就存在f[i-1][j-v[i]]
    最后，还要加上选中物品的价值w[i]。
    综上所述，如果选当前物品，则价值为f[i-1][j-v[i]]+w[i]

    然后求出它们的较大值，存在f[i][j]
    现在可以列出转移方程：

    f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);

代码

#include <bits/stdc++.h>
#define ll long long
#define N 1005
using namespace std;
inline ll read()
{
    ll x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}
    while(isdigit(c)){x=x*10+c-48;c=getchar();}
    return (f==1)?x:-x;
}//卡常
ll n=read(),V=read(),v[N],w[N],f[N][N];
int main()
{
    for(ll i=1;i<=n;i++) v[i]=read(),w[i]=read();
    for(ll i=1;i<=n;i++)
    {
        for(ll j=0;j<=V;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]);
        }//判断j是否不小于v[i]，如果小于就肯定不能选当前物品，则f[i][j]=f[i-1][j]
    }
    cout << f[n][V];
    return 0;
}

线性 DP

线性 DP 是一个大类，属于简单 DP ，没有模板，这里给一些题的题解。

最长上升子序列II(AcWing.896)

数据加强版的最长上升子序列不能直接DP，还得二分（其实有点像贪心）

思路

  1. 状态表示
    \(f_i\) 表示长度为 \(i\) 的最长上升子序列，末尾最小的数字。(长度为 \(i\) 的最长上升子序列所有结尾中，结尾最小的) 即长度为 \(i\) 的子序列末尾最小元素是什么。

  2. 状态转移
    对于每一个 \(w_i\) ， 如果大于 \(f_{ans-1}\) (下标从0开始，cnt长度的最长上升子序列，末尾最小的数字)，那就 \(ans++\) ，当前末尾最小元素为 \(w_i\) 。
    若 \(w_i\) 小于等于 \(f_{ans-1}\) ，说明不会更新当前的长度，但之前末尾的最小元素要发生变化，找到第一个大于或等于 \(w_i\)，更新以那时候末尾的最小元素。

\(f_i\) 一定以一个单调递增的数组，所以可以用二分法来找第一个大于或等于 \(w_i\) 的数字。

代码

#include <bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
inline ll read()
{
    ll x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}
    while(isdigit(c)){x=x*10+c-48;c=getchar();}
    return (f==1)?x:-x;
}//卡常
ll n=read(),l,r,ans,mid,a[N],b[N];
int main()
{
    ios::sync_with_stdio(0);cout.tie(0);
    b[0]=-1e9+5;
    for(ll i=1;i<=n;i++) a[i]=read();
    for(ll i=1;i<=n;i++)
    {
        l=0,r=ans;
        while(l<r)
        {
            mid=l+r+1>>1;
            if(b[mid]<a[i]) l=mid;
            else r=mid-1;
        }
        ans=max(ans,r+1);
        b[r+1]=a[i];
    }
    cout << ans;
    return 0;
}

最短编辑距离（AcWing.902）

说两句闲话：

  • 其实是一道字符串DP
  • 其实这道题我的最大收获是搞清楚了cin >> s+1;或scanf("%s",s+1);的必要条件是char s[N];而不是string s，怪不得之前总CE。我居然到现在才知道

思路

image

  1. 表示状态
    设f[i][j]表示 \(a\) 的前 \(i\) 个字符转换成 \(b\) 的前 \(j\) 个字符所需的最少步骤。

  2. 循环范围
    \(i\) 表示 \(a\) 的字符，\(a\) 的最大下标为 \(n\),因此 \(i\) 的循环范围是 1~\(n\) 。
    \(j\) 表示 \(b\) 的字符，\(b\) 的最大下标为 \(m\),因此 \(j\) 的循环范围是 1~\(m\) 。

  3. 状态转移
    f[i][j]的取值是Min{f[i][j-1]+1,f[i][j-1]+1,f[i-1][j-1]+1}

    其中，
    f[i][j-1]+1表示通过删字符的最小步骤；
    f[i][j-1]+1表示通过增字符的最小步骤；
    f[i-1][j-1]+1表示通过改字符的最小步骤。

    可得，转移方程为：

    f[i][j]=min(f[i][j-1],f[i][j-1])+1;
if(a[i]==b[j]) f[i][j]=min(f[i][j],f[i-1][j-1]);
else f[i][j]=min(f[i][j],f[i-1][j-1]+1);

代码

#include <bits/stdc++.h>
#define ll long long
#define N 1005
using namespace std;
inline ll read()
{
    ll x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}
    while(isdigit(c)){x=x*10+c-48;c=getchar();}
    return (f==1)?x:-x;
}//卡常
ll n,m,maxn,f[N][N];
char a[N],b[N];
void init()
{
    for(ll i=0;i<=maxn;i++)
    {
        if(i<=n) f[i][0]=i;
        if(i<=m) f[0][i]=i;
    }/*更好理解的写法：
    for(ll i=0;i<=n;i++) f[i][0]=i;//如果b的长度为0，a要转换成b只能通过删去i个字符
    for(ll i=0;i<=m;i++) f[0][1]=i;//如果a的长度为0，a要转换成b只能通过添加i个字符
*/}
int main()
{
    n=read();cin >> a+1;
    m=read();cin >> b+1;
    maxn=max(n,m);
    init();//初始化
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=m;j++)
        {
            f[i][j]=min(f[i][j-1],f[i][j-1])+1;
            if(a[i]==b[j]) f[i][j]=min(f[i][j],f[i-1][j-1]);//如果a[i]等于b[j]那就不需要再操作
            else f[i][j]=min(f[i][j],f[i-1][j-1]+1);//否则，就还需操作一次
        }
    }
    cout << f[n][m];
    return 0;
}

方格取数(luogu.P1004)

思路

  1. 状态表示
    设f[i][j][i2][j2]表示：
    第一条路走到第 \(i\) 行，第 \(j\) 列;第二条路走到第 \(i2\) 行，第 \(j2\) 列能得到的最大价值。

  2. 循环范围
    枚举都是在 \(n\)×\(n\)的方阵中，因此\(i\),\(j\),\(i2\),\(j2\)的循环范围都是 1~\(n\)。

  3. 状态转移
    和数字三角形一样，不过还是写一下。

    \(x\)：
    f[i-1][j][i2-1][j2]表示从走到上面一格能收获的最大价值。
    f[i-1][j][i2][j2-1]表示对于第一条路走到上面一格，对于第二条路走到左边一格能收获的最大价值。

    \(y\)：和 \(x\) 差不多，看代码自己理解。

    当然，要取最大值，还得加上a[i][j]和a[i2][j2]的价值。
    还有，如果路径重复，只能取一个价值。
    可得，转移方程为：

    x=max(f[i-1][j][i2-1][j2],f[i-1][j][i2][j2-1]);
y=max(f[i][j-1][i2-1][j2],f[i][j-1][i2][j2-1]);
f[i][j][i2][j2]=max(x,y)+a[i][j];
if(i!=i2||j!=j2) f[i][j][i2][j2]+=a[i2][j2];

代码

#include <bits/stdc++.h>
#define ll long long
#define N 15
using namespace std;
inline ll read()
{
    ll x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}
    while(isdigit(c)){x=x*10+c-48;c=getchar();}
    return (f==1)?x:-x;
}//卡常
ll n=read(),a[N][N],f[N][N][N][N];
void workF(ll i,ll j,ll i2,ll j2)
{
    ll x,y;
    x=max(f[i-1][j][i2-1][j2],f[i-1][j][i2][j2-1]);
    y=max(f[i][j-1][i2-1][j2],f[i][j-1][i2][j2-1]);
    f[i][j][i2][j2]=max(x,y)+a[i][j];
    if(i!=i2||j!=j2) f[i][j][i2][j2]+=a[i2][j2];
}
int main()
{
    while(1)
    {
        ll x=read(),y=read(),val=read();
        if(!x&&!y&&!val) break;
        a[x][y]=val;
    }
    for(ll i=1;i<=n;i++)
        for(ll j=1;j<=n;j++)
            for(ll i2=1;i2<=n;i2++)
                for(ll j2=1;j2<=n;j2++)
                    workF(i,j,i2,j2);
    cout << f[n][n][n][n];
    return 0;
}

传纸条(luogu.P1006)

思路

和方格取数差不多，只需改读入和循环范围。

代码

#include <bits/stdc++.h>
#define ll long long
#define N 55
using namespace std;
inline ll read()
{
    ll x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}
    while(isdigit(c)){x=x*10+c-48;c=getchar();}
    return (f==1)?x:-x;
}//卡常
ll n=read(),m=read(),a[N][N],f[N][N][N][N];
void workF(ll i,ll j,ll i2,ll j2)
{
    ll x,y;
    x=max(f[i-1][j][i2-1][j2],f[i-1][j][i2][j2-1]);
    y=max(f[i][j-1][i2-1][j2],f[i][j-1][i2][j2-1]);
    f[i][j][i2][j2]=max(x,y)+a[i][j];
    if(i!=i2||j!=j2) f[i][j][i2][j2]+=a[i2][j2];
}
int main()
{
    for(ll i=1;i<=n;i++)
        for(ll j=1;j<=m;j++)
            a[i][j]=read();
    for(ll i=1;i<=n;i++)
        for(ll j=1;j<=m;j++)
            for(ll i2=1;i2<=n;i2++)
                for(ll j2=1;j2<=m;j2++)
                    workF(i,j,i2,j2);
    cout << f[n][m][n][m];
    return 0;
}

青蛙过河（luogu.P1244）

思路

1.若有 \(k\) 个荷叶，没有石墩，则最多有 \(k+1\) 个青蛙。所以 \(f_0=k+1\) 。
2.若有 \(k\) 个荷叶，1 个石墩，则只需要使石墩上承载最多的青蛙。进一步分析，我们只需要将石墩当做对岸，这样就变成1的情况了。所以 \(f_1=f_0+k+1\) 。
3.若有 \(k\) 个荷叶，2 个石墩，则需要先让石墩 1 作为对岸，叠完后再让石墩 2 作为对岸。所以 \(f_2=f_1+f_0+k+1\) 。
继续往下推，得到转移方程：f[h]=f[0]+f[1]+f[2]+···+f[h-1]+k+1

代码

#include <bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
inline ll read()
{
    ll x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}
    while(isdigit(c)){x=x*10+c-48;c=getchar();}
    return (f==1)?x:-x;
}//卡常
ll h=read(),k=read(),f[N];
int main()
{
    f[0]=k+1;
    for(ll i=1;i<=h;i++)
    {
        f[i]+=f[0];
        for(ll j=0;j<i;j++) f[i]+=f[j];
    }
    cout << f[h];
    return 0;
}

用小学数学化简一下，可得：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
    ll x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}
    while(isdigit(c)){x=x*10+c-48;c=getchar();}
    return (f==1)?x:-x;
}//卡常
ll h=read(),k=read();
int main()
{
    cout << (k+1)*(1<<h);
    return 0;
}

NASA的食物计划（luogu.P1507）

思路

可以看做是升级版的01背包问题。

  1. 状态表示
    设f[i][j][k]表示只考虑前 \(i\) 个物品，体积不超过 \(j\)，质量不超过 \(k\) 的最大价值。
    然后会发现，\(i\) 这一层其实没有必要，就可以用二维数组存了。

  2. 循环范围
    虽然在状态表示中 \(i\) 可以不要，但在循环中 \(i\) 还是必不可少的。
    \(i\) 表示考虑前多少个物品，物品最多有 \(n\) 个，因此 \(i\) 的循环范围是 1~\(n\) 。
    \(j\) 表示可用的体积，体积最大为H，最小为h[i]，因此 \(j\) 的循环范围是 h[i]~\(H\) 。
    \(k\) 表示可用的质量，体积最大为T，最小为t[i]，因此 \(k\) 的循环范围是 t[i]~\(T\) 。

  3. 状态转移
    见01背包详解
    然后，除了体积需要腾出来，质量也得腾出来。
    这样一来，余下物品的最大体积就是f[j-h[i]][k-t[i]]
    最后，加上价值（卡路里）ka[i]

    可得，转移方程为：
    f[j][k]=max(f[j][k],f[j-h[i]][k-t[i]]+ka[i]);

代码

#include <bits/stdc++.h>
#define ll long long
#define N 505
using namespace std;
inline ll read()
{
    ll x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}
    while(isdigit(c)){x=x*10+c-48;c=getchar();}
    return (f==1)?x:-x;
}//卡常
ll H=read(),T=read(),n=read(),h[N],t[N],ka[N],f[N][N];
int main()
{
    for(ll i=1;i<=n;i++)
    {
        h[i]=read();
        t[i]=read();
        ka[i]=read();
    }
    for(ll i=1;i<=n;i++)
        for(ll j=H;j>=h[i];j--)
            for(ll k=T;k>=t[i];k--)
                f[j][k]=max(f[j][k],f[j-h[i]][k-t[i]]+ka[i]);
    //升级01背包
    cout << f[H][T];
    return 0;
}

标签：read,ll,i2,j2,while,动态,规划,getchar
From： https://www.cnblogs.com/wangxuzhou-blog/p/dynamic-programming-1.html

相关文章

  • asp.net中动态修改配置文件的方法
    很多时候，我们可能会在asp.net中动态的修改配置文件，我们可以使用如下代码中涉及到的类来完成配置文件，下面的代码是修改connectionstring的例子：System.Configuration.Configur......
  • 动态规划 背包问题算法模板
    一篇文章吃透背包问题！（细致引入+解题模板+例题分析+代码呈现）  https://leetcode.cn/problems/partition-equal-subset-sum/solution/yi-pian-wen-zhang-chi-tou-bei-b......
  • 动态规划(一)
    引入:斐波那契数列递归版本:(太慢需要优化)intf(intn){ if(n==0||n==1)return1; elsereturnf(n-1)+f(n-2);}递推版本:a[0]=a[1]=1;for(......
  • fiddler动态调试js
    背景 昨天获取到的网易云音乐站点的请求内容居然是加密的，就需要动态的调试js找出params很secSeky未加密之前的内容。调试方法 调试之前需要在目标浏览器上部署上fi......
  • 2023.1.24动态规划练习
    洛谷P1220关路灯题目描述某一村庄在一条路线上安装了\(n\)盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工......
  • 通过具体的两个例子，学习 ABAP 动态断点的使用诀窍
    本教程之前的步骤，我们学习了SAPGUI中ABAP调试器的使用方式：13.最浅显易懂的SAPGUI里ABAP调试器的使用方法介绍借助这个有用的程序调试工具，我们可以自行找到一......
  • m基于NSGAII优化算法的微网系统的多目标优化规划matlab仿真
    1.算法描述NSGA-II是基于的非支配排序的方法,在NSGA上进行改进，也是多目标进化优化领域一个里程碑式的一个算法。NSGA-Ⅱ算法是Srinivas和Deb于2000年在NSGA的基......
  • m基于NSGAII优化算法的微网系统的多目标优化规划matlab仿真
    1.算法描述       NSGA-II是基于的非支配排序的方法,在NSGA上进行改进，也是多目标进化优化领域一个里程碑式的一个算法。       NSGA-Ⅱ算法是Srinivas......
  • 我不会动态规划
    DP杂题【POI2015】洗车-Carwashes-Myjnie经典笛卡尔树上DP，设\(dp_{l,r,k}\)表示区间\([l,r]\)最小值为\(k\)的总收益，枚举最小位置\(p\)，为了避免算重，只考虑......
  • Solution 题解 UVA1389 Hard Life： 最小割，有向图，分数规划，和牛顿迭代
    题解UVA1389HardLife：最小割，有向图，分数规划，和牛顿迭代Preface黑题好耶看到了题解里面大多数是二分，我就来讲一讲简单又快速的DinkelbachAlgorithm吧！0-1分数规划......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99