头像

lilien


访客:774

离线:1天前


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

lilien
1天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
using namespace std;
const int N = 30010;
int n,m;
int f[N];
int main()
{
    cin>>m>>n;
    for(int i = 0; i < n;i++)
    {
        int v,w;
        cin>>v>>w;
        for(int j = m ; j >=v; j--)
            f[j] = max(f[j],f[j - v] +w*v);
    }
    cout<<f[m]<<endl;


    return 0;
}


活动打卡代码 AcWing 1013. 机器分配

lilien
1天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<algorithm>
using namespace std;
const int N =11,M = 16;
int n,m;
int w[N][M];
int f[N][M];
int way[N];
int main()
{
    cin>>n>>m;
    for(int i = 1; i <= n;i ++)
        for(int j = 1; j <= m ;j++)
            cin>>w[i][j];
    for(int i =1; i <=n; i ++)
        for(int j = 0; j <=m;j++)
            for(int k = 0; k <=j; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - k] +w[i][k]);

    cout<<f[n][m]<<endl;
    int j = m;
    for(int i = n; i; i--)
        for(int k =0; k <=j; k++)
            if(f[i][j]==f[i -1][j -k] +w[i][k])
            {
                way[i] = k;
                j-=k;
                break;
            }
    for(int i = 1; i <=n;i++) cout<< i <<' '<<way[i]<<endl;

    return 0;
}


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

lilien
4天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 22,M =88;
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 j = n; j>=0;j--)    
            for(int k = m; k >=0; k--)
                f[j][k] = min(f[j][k],f[max(0,j-v1)][max(0,k-v2)] + w);
    }
    cout<<f[n][m]<<endl;

    return 0;
}



lilien
4天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
using namespace std;
const int N = 110;
int n,V,M;
int f[N][N];
int main()
{
    cin>>n>>V>>M;
    for(int i = 0; i < n; i ++)
    {
        int v,m,w;
        cin>>v>>m>>w;
        for(int j =V;j>=v;j--)
            for(int k = M;k>=m;k--)
                f[j][k] = max(f[j][k],f[j - v][ k - m] +w);
    }
    cout<<f[V][M]<<endl;

    return 0;

}



lilien
4天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
// 

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

using namespace std;

const int N = 20010;

int n, m;
int f[N], g[N], q[N];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
    {
        int v, w, s;
        cin >> v >> w >> s;
        memcpy(g, f, sizeof f);
        for (int j = 0; j < v; j ++ ) //枚举所有的余数
        {
            int hh = 0, tt = -1;
            for (int k = j; k <= m; k += v)  // 枚举余数里的所有数
            {
                if (hh <= tt && q[hh] < k - s * v) hh ++ ;
                while (hh <= tt && g[q[tt]] - (q[tt] - j)/ v * w <= g[k] -( k - j )/ v * w) tt -- ; //初始的余数j
                q[ ++ tt] = k;
                f[k] = g[q[hh]] + (k - q[hh]) / v * w; //加上空余的第i个物品的w ,f(k)存放单调队列最大值,此时已判断出来f[i-1][k]是否为最大值,故直接复制不用担心被冲掉
            }
        }
    }


}



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

lilien
4天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<cstring>
#include<algorithm>
const int N = 1010;
using namespace std;
int f[N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i =0; i <n; i ++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        if(s==0)//完全背包
        {
            for(int j = v;j<=m;j++)
                f[j] = max(f[j],f[j - v] +w);
        }else
        {
            if(s==-1) s= 1;
            for(int k =1;k <=s;k*=2)
            {
                for(int j =m; j >=k *v;j--)
                    f[j] = max(f[j],f[j-k*v]+k*w);
                s-=k;
            }
            if(s)
            {
                for(int j = m; j>=s*v;j--)
                    f[j] = max(f[j],f[j - s*v]+s*w);
            }
        }
    }
    cout<<f[m]<<endl;

    return 0;
}


// 



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

lilien
4天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
using namespace std;
const int N = 6010;
int f[N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i = 0; i <n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        for(int j = m; j >0; j--)
            for(int k=0; k <=s && k*v <=j; k++)
                f[j] = max(f[j],f[j - v*k] +w*k);
    }
    cout<<f[m]<<endl;


    return 0;
}


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

lilien
8天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N =110,M = 250010;
int n;
int a[N];
int f[M];
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i = 0; i <n; i ++) cin >>a[i];
        sort(a,a + n);
        int m = a[n-1];
        memset(f,0,sizeof f);
        f[0] = 1;
        int res = 0;
        for(int i =0; i < n; i ++)
        {
            if(!f[a[i]]) res ++;
            for(int j = a[i]; j <=m; j ++)
                f[j] += f[j - a[i]];

        }
        cout<<res<<endl;

    }
    return 0;
}


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

lilien
8天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>

using namespace std;

const int N = 3010;
int n,m;
long long f[N];
int main()
{
    cin>>n>>m;
    f[0]=1;
    for(int i = 0; i < n;i++)
    {
        int v;
        cin>>v;
        for(int j = v; j <=m;j++)
            f[j]+=f[j-v];


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


活动打卡代码 AcWing 1023. 买书

lilien
8天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int N = 1010;
int v[4] ={10,20,50,100};
int f[N];
int main()
{
    int m;
    cin>>m;
    f[0] = 1;
    for(int i = 0; i < 4; i ++)
        for(int j = v[i]; j<=m;j++)
            f[j]+=f[j-v[i]];
    cout<<f[m]<<endl;


}