头像

是一个一个一个CE自动机啊啊啊啊啊啊啊啊啊啊啊啊啊

须弥教令院




离线:10小时前


最近来访(306)
用户头像
艾伦_0
用户头像
孤独的Java选手
用户头像
月下涼風
用户头像
StkOvflow
用户头像
SHArk_Ice
用户头像
闻天语
用户头像
Jettblue
用户头像
void_48
用户头像
unika
用户头像
牛旋风
用户头像
oldmomsimith
用户头像
BillyWan
用户头像
sediment
用户头像
Finn2009
用户头像
yangaich
用户头像
wt20
用户头像
jhhh
用户头像
zqw
用户头像
violet_garden
用户头像
DreamFather

活动打卡代码 AcWing 1057. 股票买卖 IV

#include <iostream>
#include <cstring>
using namespace std;
const int N=100010,M=110;
int w[N],dp[N][M][2];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    memset(dp,-0x3f,sizeof dp);
    for(int i=0;i<=n;i++)dp[i][0][0]=0;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
        dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]+w[i]);
        dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0]-w[i]);
        }

    int res=0;
    for(int i=0;i<=m;i++)res=max(res,dp[n][i][0]);
    cout<<res<<endl;
    return 0;
}



线性dp

这题根据题意不能选相邻的物品,直接列出状态转移方程

如果选:$dp[i]=dp[i-2]+w[i]$;
不选:$dp[i]=dp[i-1]$;

C++ 代码

#include <iostream>
using namespace std;
const int N=100010;
int a[N],dp[N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=2;i<=n+1;i++)scanf("%d",&a[i]);

        for(int i=2;i<=n+1;i++)dp[i]=max(dp[i-1],dp[i-2]+a[i]);

        cout<<dp[n+1]<<endl;
    }

    return 0;
}

状态机模型

这是本题的另一种思考方式:设不选为状态0,选为状态1
那么对于后一步,如果是状态0,可以由前面一步为0/1转移过来
$dp[i][0]=max(dp[i-1][0],dp[i-1][1])$
如果是状态1,只能由前面一步0转移过来
$dp[i][1]=dp[i-1][0]+w[i]$

代码

#include <iostream>
using namespace std;
const int N=100010;
int a[N],dp[N][2];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        dp[0][0]=0,dp[0][1]=-1e9;

        for(int i=1;i<=n;i++){
            dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
            dp[i][1]=dp[i-1][0]+a[i];
        }

        cout<<max(dp[n][0],dp[n][1])<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 1049. 大盗阿福

#include <iostream>
using namespace std;
const int N=100010;
int a[N],dp[N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=2;i<=n+1;i++)scanf("%d",&a[i]);


        for(int i=2;i<=n+1;i++)dp[i]=max(dp[i-1],dp[i-2]+a[i]);

        cout<<dp[n+1]<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 1236. 递增三元组

#include <iostream>
using namespace std;
typedef long long ll;
const int N=10010;
int a[N],b[N],c[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)scanf("%d",&c[i]);

    ll res=0;
    int q1=0,q2=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)if(c[j]>b[i])q1++;
        for(int k=1;k<=n;k++)if(a[k]<b[i])q2++;
        res+=q1*q2;
    }
    cout<<res<<endl;
    return 0;
}



题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。

输出 最优选法的方案数。注意答案可能很大,请输出答案模 109+7 的结果。

输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。

接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数,表示 方案数 模 109+7 的结果。

样例

数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 6
输出样例:
2

DP

这里求最优方案的方案数与 最短路 可以联系到一起去
其实这里的最优方案是价值最大的选法的数量

这里需要用一个g数组来存储到达f[i]的方法总数
f[j]只能由f[j]与f[j-v]+w转移过来,只需要判断是从什么状态转移过来即可

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
const int N=1010,mod=1e9+7;
int f[N],g[N];
int n,m;
int main()
{
    memset(f,-0x3f,sizeof f);
    f[0]=0;
    g[0]=1;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int v,w;
        scanf("%d%d",&v,&w);
        for(int j=m;j>=v;j--){
            int maxv=max(f[j],f[j-v]+w);
            int cnt=0;
            if(maxv==f[j])cnt+=g[j];
            if(maxv==f[j-v]+w)cnt+=g[j-v];
            g[j]=cnt%mod;
            f[j]=maxv;正常做一遍01背包
        }
    }

    int res=0,cnt=0;
    for(int i=0;i<=m;i++)res=max(res,f[i]);


    for(int i=0;i<=m;i++)
        if(res==f[i])
            cnt=(cnt+g[i])%mod;

    cout<<cnt<<endl;
    return 0;
}




#include <iostream>
#include <cstring>
using namespace std;
const int N=1010,mod=1e9+7;
int f[N],g[N];
int n,m;
int main()
{
    memset(f,-0x3f,sizeof f);
    f[0]=0;
    g[0]=1;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int v,w;
        scanf("%d%d",&v,&w);
        for(int j=m;j>=v;j--){
            int maxv=max(f[j],f[j-v]+w);
            int cnt=0;
            if(maxv==f[j])cnt+=g[j];
            if(maxv==f[j-v]+w)cnt+=g[j-v];
            g[j]=cnt%mod;
            f[j]=maxv;
        }
    }
    int res=0,cnt=0;
    for(int i=0;i<=m;i++)res=max(res,f[i]);


    for(int i=0;i<=m;i++)
        if(res==f[i])
            cnt=(cnt+g[i])%mod;

    cout<<cnt<<endl;
    return 0;
}



C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=25010,M=110;
int a[M],dp[N];
int main()
{
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        sort(a+1,a+1+n);


        memset(dp,0,sizeof dp);
        dp[0]=1;
        int m=a[n];

        优化主要是在下面一块区域
        int res=0;
        for(int i=1;i<=n;i++){
            if(!dp[a[i]])
            {
                这里只有当这个数不能被前面的数表示的时候,更新其他值才有意义
                否则的话是不需要用这个数更新其他值的
                例如6可以更新的数3一定可以更新,就不需要用6更新其他值了
                res++;
                for(int j=a[i];j<=N;j++)dp[j]+=dp[j-a[i]];
            }
        }
        cout<<res<<endl;
    }

    return 0;
}



题目描述

有 N 个物品和一个容量是 V 的背包。

物品之间具有依赖关系,且依赖关系组成一棵树的形状。如果选择一个物品,则必须选择它的父节点。

如下图所示:
QQ图片20181018170337.png

如果选择物品5,则必须选择物品1和2。这是因为2是5的父节点,1是2的父节点。

每件物品的编号是 i,体积是 vi,价值是 wi,依赖的父节点编号是 pi。物品的下标范围是 1…N。

求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。

输出最大价值。

输入格式
第一行有两个整数 N,V,用空格隔开,分别表示物品个数和背包容量。

接下来有 N 行数据,每行数据表示一个物品。
第 i 行有三个整数 vi,wi,pi,用空格隔开,分别表示物品的体积、价值和依赖的物品编号。
如果 pi=−1,表示根节点。 数据保证所有物品构成一棵树。

样例

输出格式
输出一个整数,表示最大价值。

数据范围
1≤N,V≤100
1≤vi,wi≤100
父节点编号范围:

内部结点:1≤pi≤N;
根节点 pi=−1;
输入样例
5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2
输出样例:
11

有依赖的背包问题:

树形dp+分组背包问题
树形dp:用数组存储树/图:链式前向星,此外,用dfs进行遍历

本题思路是:想选子节点必须选父节点,因此对于每一个父节点
只需要确定它的对应的子节点的选法即可
这里倘若再使用之前金明的预算方案的思路,就会产生$2^k$种组合情况,TLE预定

$\\$
这里如何优化呢?
可以联想到一种模型,在总限制为m情况下,父节点占用v[x],子节点就占用m-v[x]
所以可以优化成:在体积限制为m-v[x]的情况下
从k个子节点中选,价值的最大值

而k个子节点的占用v[i]也是不确定的
此时就可以通过枚举来确定

这样的话就恰好变成了分组背包问题,每个子节点是一个组,枚举选取的体积

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
const int N=110;
int h[N],ne[N],e[N],idx,dp[N][N];
int n,m;
int v[N],w[N];
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs(int x)
{
从根节点开始递归
    for(int i=h[x];i!=-1;i=ne[i]){
        int son=e[i];
        dfs(son);先计算出子节点的值

        for(int j=m-v[x];j>=0;j--)根据前面的分析,背包体积上限是m-v[x]
            for(int k=0;k<=j;k++)分组背包问题模型,枚举选第几件物品(枚举体积k)
            dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[son][k]);
            以x为根节点,体积<=j的方案的价值最大值
    }

    刚刚推出来的dp没加上v[x],还需要+v[x]
    for(int i=m;i>=v[x];i--)dp[x][i]=dp[x][i-v[x]]+w[x];
    for(int i=0;i<v[x];i++)dp[x][i]=0;体积本来就小于v[x],选不了这棵子树
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    int root=-1;
    for(int i=1;i<=n;i++){
        int p;
        cin>>v[i]>>w[i]>>p;
        if(p==-1)root=i;
        else add(p,i);
    }

    dfs(root);

    cout<<dp[root][m]<<endl;
    return 0;
}




#include <iostream>
#include <cstring>
using namespace std;
const int N=110;
int h[N],ne[N],e[N],idx,dp[N][N];
int n,m;
int v[N],w[N];
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs(int x)
{
    for(int i=h[x];i!=-1;i=ne[i]){
        int son=e[i];
        dfs(son);

        for(int j=m-v[x];j>=0;j--)
            for(int k=0;k<=j;k++)
            dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[son][k]);

    }

    for(int i=m;i>=v[x];i--)dp[x][i]=dp[x][i-v[x]]+w[x];
    for(int i=0;i<v[x];i++)dp[x][i]=0;
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    int root=-1;
    for(int i=1;i<=n;i++){
        int p;
        cin>>v[i]>>w[i]>>p;
        if(p==-1)root=i;
        else add(p,i);
    }

    dfs(root);

    cout<<dp[root][m]<<endl;
    return 0;
}


活动打卡代码 AcWing 7. 混合背包问题

#include <iostream>
using namespace std;
const int N=1010;
int dp[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int v,w,s;
        scanf("%d%d%d",&v,&w,&s);
        if(s==0)
            for(int j=v;j<=m;j++)
                dp[j]=max(dp[j],dp[j-v]+w);

        else{
            s=abs(s);
            for(int k=1;k<=s;k*=2){
                for(int j=m;j>=k*v;j--)
                    dp[j]=max(dp[j],dp[j-v*k]+w*k);
                s-=k;
            }
            if(s)
            {
                for(int j=m;j>=s*v;j--)
                    dp[j]=max(dp[j],dp[j-v*s]+w*s);
            }
        }
    }
    cout<<dp[m]<<endl;

    return 0;
}