头像

Belinda_与风逐梦

绝对互关 好闺蜜:Iris_随月浅唱




离线:1个月前


最近来访(199)
用户头像
1176927355@qq.com
用户头像
Escort
用户头像
someone
用户头像
等雨停
用户头像
lyktes
用户头像
乐天知命故不忧
用户头像
yys_c
用户头像
索隆
用户头像
leimingze
用户头像
嘴平衡之助
用户头像
时光中有你
用户头像
Kev_4
用户头像
垫底抽风
用户头像
唐海洋
用户头像
沙漠之狐
用户头像
konng
用户头像
zyj..
用户头像
潘潘_the_panda
用户头像
浮生若梦ღ
用户头像
今晚打老虎_7


只是粗略地理解了一下,想念在家看y总视频的日子……

至少我会打了不是吗

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1010;
char a[N],b[N];
int dp[N][N];
//dp[i][j]表示a[]前i个字符中和b[]前j个字符的最长公共子序列
int main()
{
    int n,m;
    cin>>n>>m;//输入长度
    scanf("%s%s",a+1,b+1);//下标从1开始
    for(int i=1;i<=n;i++)//遍历a字符串
    {
        for(int j=1;j<=m;j++)//遍历b字符串
        {
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            //第一种是不包含a[i]包含b[j],第二种是包含a[i]不包含b[j]
            //因为这两种一定会存在,所以直接更新就行
            if(a[i]==b[j])//因为当前这两个字符一样,那么就可以加入到最长公共子序列里,也就是不包含a[i]和b[j]然后长度加上1
                dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
        }
    }
    cout<<dp[n][m];
    return 0;
}



#include<iostream>
#include<cstring>
using namespace std;
const int N=310;
int n,m;
int g[N][N];
int f[N][N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int dp(int x,int y)
{
    int &v=f[x][y];
    if(v!=-1) return v;//如果不是初始化,就证明之前已经进行过计算,直接返回
    v=1;
    for(int i=0;i<4;i++)//枚举4个方向
    {
        int a=x+dx[i],b=y+dy[i];//取更新后的坐标
        if(a>=1&&a<=n&&b>=1&&b<=m&&g[x][y]>g[a][b])//判断是否合法
            v=max(v,dp(a,b)+1);//进行状态转移
    }
    return v;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[i][j];//输入
    memset(f,-1,sizeof f);
    int res=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            res=max(res,dp(i,j));//进行状态转移
    cout<<res;
    return 0;
}



#include<cstring>
#include<iostream>
using namespace std;
const int N=6010;
int n;
int happy[N];//快乐指数
int h[N], e[N], ne[N], idx;//链式前向星
int f[N][2];//两种状态
//f[i][0]表示不选择i这个点的最大快乐指数
//f[i][1]表示选择第i这个点的最大快乐指数
bool fa[N];//记录有没有父结点
void add(int a,int b)//建边
{
    idx++;
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
}
void dfs(int u)
{
    f[u][1]=happy[u];//因为选择当前这个点,所以要先加上当前这个点的快乐指数
    for(int i=h[u];i;i=ne[i])//遍历子结点
    {
        int j=e[i];//取出子结点
        dfs(j);//遍历
        f[u][0]+=max(f[j][0],f[j][1]);//如果当前这个点不选,那么他的子结点就可以有两种状态
        f[u][1]+=f[j][0];//如果选择了当前这个点,那么他的子结点就不能选了
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>happy[i];//快乐指数
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;//b是a的上司(父节点)
        fa[a]=1;
        add(b,a);//因为父节点在前,所以反过来
    }
    int root=1;//因为节点是1~n所以root(根)从1开始找
    while(fa[root]) root++;//如果当前这个结点有父结点,就证明不是根结点,就继续往后寻找
    dfs(root);//遍历(准确的说是进行树形dp)
    cout<<max(f[root][0],f[root][1]);//取最大值
}



#include<iostream>
using namespace std;
const int N=1010;
int a[N],dp[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        dp[i]=1;//就算前面没有比当前数再小的数还有他自己
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i])//如果前面有比他再小的数
                dp[i]=max(dp[i],dp[j]+1);//将自身和以前面的那个数为结尾的最长长度+1取一个最大值
        }
    }
    int res=0;
    for(int i=1;i<=n;i++) if(res<dp[i]) res=dp[i];
    cout<<res;
    return 0;
}

记录最长上升子序列的写法

#include<iostream>
using namespace std;
const int N=1010;
int a[N],f[N],g[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        f[i]=1;//就算前面没有比当前数再小的数还有他自己
        g[i]=0;
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i])//如果前面有比他再小的数
                if(f[i]<f[j]+1)//比较哪一种比较长
                {
                    f[i]=f[j]+1;
                    g[i]=j;//记录当前这个数是由j转移过来的
                }
        }
    }
    int k=1;
    for(int i=1;i<=n;i++)
    {
        if(f[k]<f[i])//找到最后最长的子序列的结尾
            k=i;
        // cout<<f[k]<<' ';
    }
    cout/*<<endl*/<<f[k]<<endl;//输出最长是多少
    int res=0,cnt=0,b[N];
    for(int i=0,len=f[k];i<len;i++)
    {
        b[cnt++]=a[k];//进行记录
        k=g[k];//因为记录的当前这个数转移过来的钱的那个数,以此类推,最后一路的序列是倒序的
    }
    for(int i=cnt-1;i>=0;i--) cout<<b[i]<<' ';//因为记录是倒序的,所以要倒序输出(负负为正)
    return 0;
}



从上往下走

#include<iostream>
using namespace std;
const int N=510,INF=1e9;
int a[N][N],dp[N][N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin>>a[i][j];//输入

    for(int i=0;i<=n+1;i++)
        for(int j=0;j<=i+1;j++)
            dp[i][j]=-INF;//初始化为最小值

    dp[1][1]=a[1][1];//初始化,因为从(1,1)开始

    for(int i=2;i<=n;i++)
        for(int j=1;j<=i;j++)
            dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];//往左走或者往右走

    int maxx=-INF;
    for(int j=1;j<=n;j++)
        if(maxx<dp[n][j]) maxx=dp[n][j];//在最后一行中找到一个最大值
    cout<<maxx;
    return 0;
}

从下往上走

#include<iostream>
using namespace std;
const int N=510;
int f[N][N];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin>>f[i][j];//输入

    for(int i=n-1;i>=1;i--)
        for(int j=1;j<=i;j++)
            f[i][j]+=max(f[i+1][j],f[i+1][j+1]);//往左边上来的或者从右边上来的

    cout<<f[1][1];//最后会上到(1,1)
    return 0;
}



#include<iostream>
using namespace std;
const int N=110;
int n,m;
int v[N][N],w[N][N],s[N];
int f[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)//组数
    {
        cin>>s[i];//当前组里面有多少个物品
        for(int j=0;j<s[i];j++)//当前组的每一个物品的体积以及价值
        {
            cin>>v[i][j]>>w[i][j];
        }
    }
    for(int i=1;i<=n;i++)//第i组
    {
        for(int j=m;j>=0;j--)//体积
        {
            for(int k=0;k<s[i];k++)//第k个
                if(v[i][k]<=j)//如果当前的物品的体积不大于j,那么符合要求,可以进行状态转移
                    f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
        }
    }
    cout<<f[m];
    return 0;
}



二进制优化

#include<iostream>
using namespace std;
const int N=12010,M=2010;
int n,m;
int v[N],w[N],dp[M];
int main()
{
    cin>>n>>m;
    int cnt=0;//记录一下当前的数组记录到了第几位
    for(int i=1;i<=n;i++)//第i个物品
    {
        int a,b,s;//体积,价值,个数
        cin>>a>>b>>s;
        int k=1;//从1开始枚举,进行二进制拆分
        while(k<=s)
        {
            cnt++;//每拆分出来一个二进制,就要进行记录,从数组里面腾出来一个位置
            v[cnt]=a*k;//那么当前这里就是选择了k个物品所需要的体积
            w[cnt]=b*k;//这里就是选择了k个物品的价值
            s-=k;//因为时进行二进制拆分,每拆出来一个数,就要减掉这个数
            k*=2;//二进制,所以要乘以2
        }
        if(s>=0)//如果到最后还有剩余,再进行特殊的记录
        {
            cnt++;
            v[cnt]=a*s;
            w[cnt]=b*s;
        }
    }
    n=cnt;//因为是二进制拆分,所以拆出来的所有数都可以重新凑成从0~n,直接进行01背包
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=v[i];j--)
        {
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[m];
    return 0;
}



朴素做法

#include<iostream>
using namespace std;
const int N=110;
int v[N],w[N],dp[N][N],s[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<=s[i]&&k*v[i]<=j;k++)//保证枚举的个数不超过一共有的个数,并且所选取的k个物品的体积不超过背包的总体积
            {
                    dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);//在所有情况中寻找一个最大的情况
            }
        }
    }
    cout<<dp[n][m];
    return 0;
}

优化做法见AcWing 5. 多重背包问题 II




朴素做法

#include<iostream>
using namespace std;
const int N=1010;
int v[N],w[N],dp[N][N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            dp[i][j]=dp[i-1][j];//这种情况一定存在,所以直接赋成这个值
            if(j>=v[i])//如果合法,就进行状态转移
                dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
                //当选择第i个物品的时候,因为有无限多个,可能原来也选择了第i个物品,所以不用i-1,还就是选择这前i个物品
        }
    }
    cout<<dp[n][m];
    return 0;
}

优化做法

#include<iostream>
using namespace std;
const int N=1010;
int v[N],w[N],dp[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
    {
        //其实大致上和01背包差不多
        for(int j=v[i];j<=m;j++)//但是这里要注意一下
        //在01背包中特意强调过这里是进行倒序的循环对叭
        //但是这里就不一样了,直接正序进行循环就可
        //因为01背包用的是上一层的数值,完全背包用的正好是循环过后更新了的数值
        {
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[m];
    return 0;
}



朴素做法

#include<iostream>
using namespace std;
const int M=1010;
int v[M],w[M],dp[M][M];
//v[i]表示第i个物品的体积
//w[i]表示第i个物品的价值
//dp[i][j]表示前i个物品在体积不大于j的情况下的最大值
int main()
{
    int N,V;
    cin>>N>>V;
    for(int i=1;i<=N;i++)
        cin>>v[i]>>w[i];
    for(int i=1;i<=N;i++)
        for(int j=1;j<=V;j++)
        {
            dp[i][j]=dp[i-1][j];//一定会更新,因为就算不选,就会是上一次得到的数
            if(v[i]<=j)//如果体积≤j,证明符合要求,就可往下进行
                dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);//在选和不选中选择一个一个最大的
                //选的时候,要先找到不放第i个物体的时候的最大值,所以要j-v[i],然后再加上第i个物品的价值
        }
    cout<<dp[N][V];//输出最后结果
    return 0;
}

优化做法

#include<iostream>
using namespace std;
const int N=1010;
int v[N],w[N],f[N];
//v[i]表示第i个物品的体积
//w[i]表示第i个物品的价值
//dp[j]表示前i个物品(在循环中体现)在体积不大于j的情况下的最大值
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
        for(int j=m;j>=v[i];j--)//因为每一次循环需要调用上一次循环中的数据
        //因为j-v[i]一定小于j,所以j-v[i]一定会在j之前更新
        //为了防止更新时用的不是真正的数据,所以要进行倒序遍历
        //dp[j]=dp[j]//因为第一维省略掉,所以这一句话就没什么用,直接省略
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[m];
    return 0;
}