个人空间 - AcWing

富贵

安徽大学

关注数

粉丝数

阅读量

570

+关注发消息

离线：8小时前

最近来访(57)

三三得玖

栏杆拍遍的咸鱼

嘻嘻哈哈嘻嘻

达不溜了

JcWing

开心胖头愚

Hacker_King

小余锅锅

山猪

陌上花开Charlie

WangJY

_Null_

磨糖fly

great_Wall

maolibo

no_uid_acwing

su尔

手撕蓝莓酥

小雪菜小G总

hpstory

新鲜事原文

富贵
10小时前

终于把线性DP+KMP自动机模型搞懂了

活动打卡代码 AcWing 1052. 设计密码

富贵
14小时前

                #include<iostream>
#include<cstring>

using namespace std;

const int N=55,mod=1e9+7;

int n,m;
char s[N];
int f[N][N],ne[N];

int main(){
    cin>>n>>s+1;
    m=strlen(s+1);
    //KMP预处理前缀表
    for(int i=2,j=0;i<=m;i++){
        while(j&&s[i]!=s[j+1]) j=ne[j];
        if(s[i]==s[j+1]) j++;
        ne[i]=j;
    }
    //DP
    f[0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            for(char ch='a';ch<='z';ch++){
                int ptr=j;
                while(ptr&&s[ptr+1]!=ch) ptr=ne[ptr];
                if(s[ptr+1]==ch) ptr++;
                f[i+1][ptr]=(f[i+1][ptr]+f[i][j])%mod;
            }
        }
    }
    //统计所有的目标状态
    int res=0;
    for(int j=0;j<m;j++)
    res=(res+f[n][j])%mod;

    cout<<res<<endl;

}

            

活动打卡代码 AcWing 1058. 股票买卖 V

富贵
19小时前

                #include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int n;
int w[N];
int f[N][3];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> w[i];

    memset(f, -0x3f, sizeof f);//初始化很重要
    f[0][0] = 0;//初始化很重要
    for (int i = 1; i <= n; ++ i)
    {
        f[i][0] = max(f[i - 1][0], f[i - 1][2]);
        f[i][1] = max(f[i - 1][1], f[i - 1][0] - w[i]);
        f[i][2] = f[i - 1][1] + w[i];
    }
    cout << max(f[n][0], f[n][2]) << endl;
    return 0;
}

            

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

富贵
19小时前

                #include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=100010,M=110;

int n,m;
int w[N];
int f[N][M][2];
//f[i][j][0]：第i天，已经进行完j次交易后的最大利润
//f[i][j][1]：第i天，正在进行第j次交易（已经进行了j - 1次交易）后的最大利润
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>w[i];

    memset(f,-0x3f,sizeof f);//初始化很重要
    for(int i=0;i<=n;i++)
    f[i][0][0]=0;//初始化很重要

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+w[i]);//卖出
            f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-w[i]);//买入
        }
    }

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

            

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

富贵
21小时前

                #include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=1e5+10,INF=0x3f3f3f3f;

int n;
int w[N];
int f[N][2];//考虑前i家店铺，当前第i家店铺选择偷(j=1)或者不偷(j=0)的方案

void solve(){

    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>w[i];
    for(int i=1;i<=n;i++){
        f[i][0]=max(f[i-1][1],f[i-1][0]);
        f[i][1]=f[i-1][0]+w[i];
    }
    cout<<max(f[n][0],f[n][1])<<endl;
}
int main(){
    //f[0][0]=0;
    //f[0][1]=-INF;
    int T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}

            

活动打卡代码 AcWing 487. 金明的预算方案

富贵
22小时前

有依赖背包，关系是一个森林，用树形DP做会超时。注意到题目中有提到，每个主件的附属品数量不超过2个，且附物品不会再有附属品。
因此我们可以采用分组背包对本题的状态进行集合划分，每组物品四种组合情况，枚举时采用二进制思想。
这里还用到了typedef ， vector，通过此题学习他们的用法

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

#define v first
#define w second

using namespace std;

typedef pair<int ,int >PII;

const int N=62,M=32010;

int n,m;
PII master[N];
vector<PII> servent[N];
int f[M];

int main(){
    cin>>m>>n;

    for(int i=1;i<=n;i++){
        int v,p,q;
        cin>>v>>p>>q;
        p*=v;
        if(!q) master[i]={v,p};
        else servent[q].push_back({v,p});
    }

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

        for(int u=m;u>=0;u--){

            for(int j=0;j<1<<servent[i].size();j++){

                int v=master[i].v,w=master[i].w;

                for(int k=0;k<servent[i].size();k++){

                    if(j>>k&1){
                        v+=servent[i][k].v;
                        w+=servent[i][k].w;
                    }

                }
                if(u>=v)
                f[u]=max(f[u],f[u-v]+w);
            }
        }
    }
cout<<f[m]<<endl;
}

题解 AcWing 487. 金明的预算方案（分组背包+二进制思想解决有依赖背包问题）

富贵
22小时前

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

#define v first
#define w second

using namespace std;

typedef pair<int ,int >PII;

const int N=62,M=32010;

int n,m;
PII master[N];
vector<PII> servent[N];
int f[M];

int main(){
    cin>>m>>n;

    for(int i=1;i<=n;i++){
        int v,p,q;
        cin>>v>>p>>q;
        p*=v;
        if(!q) master[i]={v,p};
        else servent[q].push_back({v,p});
    }

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

        for(int u=m;u>=0;u--){

            for(int j=0;j<1<<servent[i].size();j++){

                int v=master[i].v,w=master[i].w;

                for(int k=0;k<servent[i].size();k++){

                    if(j>>k&1){
                        v+=servent[i][k].v;
                        w+=servent[i][k].w;
                    }

                }
                if(u>=v)
                f[u]=max(f[u],f[u-v]+w);
            }
        }
    }
cout<<f[m]<<endl;
}

活动打卡代码 AcWing 734. 能量石

富贵
1天前

价值随时间损失+邻项交换+01背包
因为该01背包问题的物品价值随时间损失，所以要邻项交换求枚举物品的最佳次序

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

//邻项交换
struct Node{
    int s,e,l;
    bool operator< (const Node& t) const{
        return s*t.l<t.s*l;
    }
}a[110];

int T,n,m;
int f[100010];//考虑前 i 个魔法石，且吃掉最后一个魔法石后，所用总时间恰好为 j 的方案

void solve(){
    memset(f,-0x3f,sizeof f);//和状态的定义有关，本题状态定义是恰好，如果是不超过的话可以只初始化成0即可
    f[0]=m=0;

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].s>>a[i].e>>a[i].l;
        m+=a[i].s;
    }
    sort(a+1,a+n+1);//排序物品的遍历顺序（邻项交换）

    for(int i=1;i<=n;i++){
        for(int j=m;j>=a[i].s;j--){
            int pre=j-a[i].s;
            f[j]=max(f[j],f[pre]+a[i].e-pre*a[i].l);
        }
    }

    int res=0;
    //因为状态定义为恰好，故要遍历所有时间
    for(int j=0;j<=m;j++){
        res=max(res,f[j]);
    }
    cout<<res<<endl;
}

int main(){
    int t=1;
    cin>>T;
    while(T--){
        cout<<"Case #"<<t++<<": ";//": "输出格式为Case #1:12  若改为":"则输出格式为Case #1: 12
        solve();
    }
    return 0;
}

题解 AcWing 734. 能量石(价值随时间损失+邻项交换+01背包)

富贵
1天前

价值随时间损失+邻项交换+01背包
因为该01背包问题的物品价值随时间损失，所以要邻项交换求枚举物品的最佳次序

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

//邻项交换
struct Node{
    int s,e,l;
    bool operator< (const Node& t) const{
        return s*t.l<t.s*l;
    }
}a[110];

int T,n,m;
int f[100010];//考虑前 i 个魔法石，且吃掉最后一个魔法石后，所用总时间恰好为 j 的方案

void solve(){
    memset(f,-0x3f,sizeof f);//和状态的定义有关，本题状态定义是恰好，如果是不超过的话可以只初始化成0即可
    f[0]=m=0;

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].s>>a[i].e>>a[i].l;
        m+=a[i].s;
    }
    sort(a+1,a+n+1);//排序物品的遍历顺序（邻项交换）

    for(int i=1;i<=n;i++){
        for(int j=m;j>=a[i].s;j--){
            int pre=j-a[i].s;
            f[j]=max(f[j],f[pre]+a[i].e-pre*a[i].l);
        }
    }

    int res=0;
    //因为状态定义为恰好，故要遍历所有时间
    for(int j=0;j<=m;j++){
        res=max(res,f[j]);
    }
    cout<<res<<endl;
}

int main(){
    int t=1;
    cin>>T;
    while(T--){
        cout<<"Case #"<<t++<<": ";//": "输出格式为Case #1:12  若改为":"则输出格式为Case #1: 12
        solve();
    }
    return 0;
}

活动打卡代码 AcWing 12. 背包问题求具体方案

富贵
1天前

求状态转移路径问题只能用二维做
本题为01背包求状态转移路径（本题还要求字典序输出，故逆序遍历）
二维01背包模板（与一维区别很大）：

 for (int i = n; i >= 1; -- i)
    {
        for (int j = 0; j <= m; ++ 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]);
        }
    }

本题代码：

#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int w[N], v[N];
int f[N][N];
int path[N], cnt=0;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) 
    cin >> v[i] >> w[i];

    for (int i = n; i >= 1; -- i)
    {
        for (int j = 0; j <= m; ++ 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]);
        }
    }

    int j = m;
    for (int i = 1 ; i <= n; ++ i)
    {
        if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i])
        {
            path[cnt ++ ] = i;
            j -= v[i];
        }
    }

    for (int i = 0; i < cnt; ++ i) 
    cout << path[i] << " ";
}

2 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论