头像

CB


访客:14433

离线:5天前



CB
14天前

Day 1:做了两数相除。



活动打卡代码 AcWing 426. 开心的金明

CB
25天前
//就是一个简单的01背包问题,直接就交了
#include<iostream>
using namespace std;

//不超过N元
const int N=30010;
int dp[N];

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

    int v[m+1];
    int p[m+1];
    for(int i=1;i<=m;i++)
    {
        cin>>v[i]>>p[i];
    }

    for(int i=1;i<=m;i++)
    {
        for(int j=n;j>=v[i];j--)
        {
            dp[j]=max(dp[j],dp[j-v[i]]+v[i]*p[i]);
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}


活动打卡代码 AcWing 1020. 潜水员

CB
26天前
#include <cstring>
#include <iostream>

using namespace std;

const int N = 22, M = 80;

int n, m, K;
int f[N][M];

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

    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;

    while (K -- )
    {
        int v1, v2, w;
        cin >> v1 >> v2 >> w;
        for (int i = n; i >= 0; i -- )
            for (int j = m; j >= 0; j -- )
                f[i][j] = min(f[i][j], f[max(0, i - v1)][max(0, j - v2)] + w);
    }


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

    return 0;
}





CB
1个月前
#include<iostream>
using namespace std;
const int N=1010;
//const int V=110;
const int R=110;

int V[N];
int M[N];
int W[N];
//二维费用的dp问题(01背包)
//三维dp,很简单
int dp[N][R][R];

int main(){

    int n,v,m;
    cin>>n>>v>>m;
    for(int i=1;i<=n;i++)
    {
        //vi,mi,wi:体积,重量,价值
        int a,b,c;
        cin>>a>>b>>c;

        V[i]=a;
        M[i]=b;
        W[i]=c;
    }
    int ret=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=v;j++)
        {
            for(int l=0;l<=m;l++)
            {
                if(V[i]<=j && M[i]<=l) dp[i][j][l]=max(dp[i-1][j][l],dp[i-1][j-V[i]][l-M[i]]+W[i]);
                //不符合条件的时候,一定不要忘记赋初值
                else dp[i][j][l]=dp[i-1][j][l];
            }
        }
    }
    cout<<dp[n][v][m]<<endl;
    return 0;
}


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

CB
1个月前
//用这种方式提交有一个case过不了~~~~~
#include<iostream>
using namespace std;
const int N=13010;
const int V=1010;
#include<vector>
int dp[V];
struct Thing{
    int s;
    int v,w;
};
//用vector吧这里,比单纯维护一个数组方便很多
vector<Thing> things;

int main(){

    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
       int v,w,s;
       cin>>v>>w>>s;
       if(s==-1) things.push_back({-1,v,w});
       if(s==0) things.push_back({0,v,w});
       else{
           //对于多重背包单独处理一下
           for(int k=1;k<=s;k*=2)
           {
               things.push_back({-1,v*k,w*k});
               s-=k;
           }
           if(s>0)
           {
               things.push_back({-1,v*s,w*s});
           }
       }
    }

    int size=things.size();
    for(int i=1;i<=size;i++)
    {
        if(things[i].s==-1)
        {
            //完全背包从小到大开始枚举
            for(int j=things[i].v;j<=m;j++) dp[j]=max(dp[j],dp[j-things[i].v]+things[i].w);
        }
        else {
            for(int j=m;j>=things[i].v;j--) dp[j]=max(dp[j],dp[j-things[i].v]+things[i].w);
        }
    }

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


活动打卡代码 AcWing 5. 多重背包问题 II

CB
1个月前
//下面是我一开始的提交,是下面这个样子,只能过50%的case
#include<iostream>
using namespace std;
//这个地方一定要注意的一个点就是,你把原始的1000规模的物品数,每个物品拆成多个以后,
//你的N其实扩大了很多,所以不能再用1010了,否则很多大的case无法通过
const int N=12010;
const int M=2010;

int dp[M];
int V[N];
int W[N];

int main(){

   int n,m;
   cin>>n>>m;

   int cnt=0;
   for(int i=1;i<=n;i++)
   {
       int v,w,s;
       cin>>v>>w>>s;
       //对于每一个s枚举一下
       for(int k=1;k<=s;k*=2)
       {
           cnt++;
           V[cnt]=v*k;
           W[cnt]=w*k;
           s-=k;
           //cnt++;
       }
       if(s>0)
       {
           cnt++;
           V[cnt]=v*s;
           W[cnt]=w*s;
       }
   }

   //开始01背包
   //cout<<"cnt is ===="<<cnt<<endl;
   for(int i=1;i<=cnt;i++)
   {
       for(int j=m;j>=V[i];j--)
       {
           dp[j]=max(dp[j],dp[j-V[i]]+W[i]);
       }
   }
    cout<<dp[m]<<endl;

    return 0;
}




活动打卡代码 AcWing 1019. 庆功会

CB
1个月前
#include<iostream>
using namespace std;
int n,m;
const int N=510;
const int M=6010;
//V W S
int V[N];
int W[N];
int S[N];
int dp[N][M];

int main(){
    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++)
            {
                dp[i][j]=max(dp[i][j],dp[i-1][j-k*V[i]]+k*W[i]);
            }
        }
    }
    cout<<dp[n][m]<<endl;

    return 0;
}


活动打卡代码 AcWing 1019. 庆功会

CB
1个月前
#include<iostream>
using namespace std;
int n,m;
const int N=510;
const int M=6010;
//V W S
int V[N];
int W[N];
int S[N];
int dp[N][M];

int main(){
    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++)
            {
                dp[i][j]=max(dp[i][j],dp[i-1][j-k*V[i]]+k*W[i]);
            }
        }
    }
    cout<<dp[n][m]<<endl;

    return 0;
}


活动打卡代码 AcWing 532. 货币系统

CB
1个月前
//我一开始用原始的完全背包的写法,没能正确实现,报了段错误
#include<iostream>
using namespace std;
#include<algorithm>
#include<string.h>
const int N=110;
//NOIP的题目一般都很有思考性,就是你得先思考出一些性质出来
//我对于思考这些性质就不够具体和数学化,浮在感觉表面
//灿神抽象出了两条性质
//一条是原始的a1,a2,a3....都可以被表示出来
//二条是b1,b2,b3...一定来源于a1,a2,a3...
//这题特么的有点像特征选择

//由于第二条性质的存在,所以我们的这个问题本质上不是一个最优化问题也不是一个贪心问题
//而是一个确定的多重背包问题
//也即答案一定在原始a数组里面,你只需要去剔除掉一些就可以,而不是从海量整数中再去重新找
//所以对于数组里面的某个数:如果可被表示那么一定不能去选
//如果不能被表示,那么一定要去选

int arr[N];
const int M=25010;
int dp[N][M];
bool flag[N];

int wanquanbeibao(int* arr,int n,bool* flag)
{
    sort(arr,arr+n);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            for(int l=0;l<=arr[i];l++)
            {

                for(int k=0;k<=l/arr[j];k++)
                {
                    dp[j][arr[i]]+=dp[j-1][arr[i]-k*arr[j]];
                }

            }
            if(dp[j][arr[i]]) flag[i]=true;
        }
        //为true的就代表可以被其它的表示,那么就把这个数删除
    }

    int ret=0;
    for(int i=0;i<n;i++)
    {
        if(!flag[i]) ret++;
    }
    return ret;
}


int main(){

    int T;
    cin>>T;

    while(T--)
    {
        //memset(flag,false,sizeof flag);
        int n;
        cin>>n;
        for(int i=0;i<n;i++) cin>>arr[i];  
        for(int i=0;i<n;i++) cout<<arr[i]<<endl;
        cout<<wanquanbeibao(arr,n,flag)<<endl;

    }
    return 0;
}

//用灿神的完全背包的一维试试


活动打卡代码 AcWing 1021. 货币系统

CB
1个月前
//多重背包不用说
//需要注意一个问题:如果出现这个错误1586760475,然而真实值是4919324314395
//这个时候是不是可以考虑下是不是数值爆炸的问题,即把int类型换成ll类型

#include<iostream>
using namespace std;
const int N=20;
int arr[N];
const int M=3010;
typedef  long long LL;
LL dp[N][M];

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

    dp[0][0]=1;

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<=j/arr[i];k++)
            {
               dp[i][j]+=dp[i-1][j-k*arr[i]];            
            }
        }
    }

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