头像

啊哈哈1




离线:10小时前


最近来访(10)
用户头像
snvxv
用户头像
顺其自然_0
用户头像
su尔
用户头像
诚_7
用户头像
._782
用户头像
ZarroBoog
用户头像
听雨-情殇
用户头像
October003
用户头像
上下求索
用户头像
curl.


啊哈哈1
14小时前
#include<bits/stdc++.h>
using namespace std;
const int N=32010;
int f[N],n,m,v[N],w[N];
vector<int>z;
vector<vector<int>>fu(N);
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        int vs,p,q;
        cin>>vs>>p>>q;
        v[i]=vs;
        w[i]=p*vs;
        if(q==0)z.push_back(i);
        else fu[q].push_back(i);
    }



    int u=z.size();
    //for(int i=0;i<u;i++)cout<<z[i];
    //cout<<fu[1][0]<<fu[1][1];
    for(int i=0;i<u;i++){
        int t=z[i];
        int e=fu[t].size();

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


            for(int k=0;k< 1<<e ;k++){//最多4种情况二进制表示则对应0(00),1(01),2(10),3(11);

                int v2=v[t],w2=w[t];

                for(int r=0;r<e;r++){
                    if(k >> r & 1){
                        v2+=v[fu[t][r]];
                        w2+=w[fu[t][r]];
                    }
                }

                if(j>=v2)f[j]=max(f[j],f[j-v2]+w2);
            }
        }
    }
    cout<<f[m];
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

啊哈哈1
22小时前
//{e - (j - s) * l }< 0 也是没问题的,因为我们是把顺序排好后的能量石的所有可能组合全遍历了一遍,就算小于0,后面有比他大的也会替换掉
//这个题用 恰好 是因为能量石的能量会随着时间的不同而改变,普通01背包问题之所以能用至多和至少是因为物品价值不会随体积变化而变化
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int T,f[N];
struct Nls{
    int s,e,l;
    bool operator  < (const Nls &w)const{
        return s*w.l<w.s*l;
    }
}nls[N];
int main(){
    cin>>T;
    int u=1;
    while(T--){
        int n,m;
        cin>>n;
        m=0;
        for(int i=0;i<n;i++){
            int s,e,l;
            cin>>s>>e>>l;
            nls[i]={s,e,l};
            m+=s;
        }
        sort(nls,nls+n);

        //这个题用 恰好 是因为能量石的能量会随着时间的不同而改变,普通01背包问题之所以能用至多和至少是因为物品价值不会随体积变化而变化
        memset(f,-0x3f,sizeof f);
        f[0]=0;

        for(int i=0;i<n;i++){
            int s=nls[i].s,e=nls[i].e,l=nls[i].l;
            for(int j=m;j>=s;j--){
                f[j]=max(f[j],f[j-s]+e-(j-s)*l);//{e - (j - s) * l }< 0 也是没问题的,因为我们是把顺序排好后的能量石的所有可能组合全遍历了一遍,就算小于0,后面有比他大的也会替换掉
            }
        }
        int res=0;
        for(int i=0;i<=m;i++)res=max(res,f[i]);
        cout<<"Case #"<<u<<": "<<res<<endl;
        u++;
    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 737. 数组替换

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sy=new Scanner(System.in);
        int[] s=new int[10],b;
        for(int i=0;i<10;i++)s[i]=sy.nextInt();
        for(int i=0;i<10;i++){
            if(s[i]<=0)s[i]=1;
        }
        for(int i=0;i<10;i++){
        System.out.printf("X[%d] = %d\n",i,s[i]);
        }

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



#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[N],w[N];
int f[N][N],n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    for(int i=n;i;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]){
            cout<<i<<" ";
            j-=v[i];
        }
    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



#include<bits/stdc++.h>
using namespace std;
const int N=1010,mod=1e9+7;
int f[N],g[N],n,m;
int main(){
    cin>>n>>m;
    memset(f,-0x3f,sizeof f);
    f[0]=0;
    g[0]=1;
    for(int i=0;i<n;i++){
        int v,w;
        cin>>v>>w;
        for(int j=m;j>=v;j--){
           int maxx=max(f[j],f[j-v]+w);
           int cnt=0;
           if(f[j]==maxx)cnt+=g[j];
           if(f[j-v]+w==maxx)cnt+=g[j-v];
           g[j]=cnt%mod;
           f[j]=maxx;
        }
    }

    int res=0;
    for(int i=0;i<=m;i++)res=max(f[i],res);
    int cnt=0;
    for(int i=0;i<=m;i++){
        if(res==f[i])cnt+=g[i];
    }
    cout<<cnt;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



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

        for(int j=m-v[u];j>=0;j--){
            for(int k=0;k<=j;k++){
                f[u][j]=max(f[u][j],f[u][j-k]+f[son][k]);
            }
        }
    }
    for(int i=m;i>=v[u];i--)f[u][i]=f[u][i-v[u]]+w[u];
    for(int i=0;i<v[u];i++)f[u][i]=0;
}
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    int root;
    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<<f[root][m];
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

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


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

#include<bits/stdc++.h>
using namespace std;
const int N=25;
int n,m;
int s[N][N],f[N][N],w[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>s[i][j];
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];
            for(int k=1;k<=j;k++){
                f[i][j]=max(f[i][j],f[i-1][j-k]+s[i][k]);
            }
        }
    }
    cout<<f[n][m]<<endl;

    int j=m;
    for(int i=n;i;i--){
        for(int k=1;k<=j;k++){
            if(f[i][j]==f[i-1][j-k]+s[i][k]){
                w[i]=k;
                j-=k;
                break;
            }
        }
    }
    for(int i=1;i<=n;i++)cout<<i<<" "<<w[i]<<endl;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,k,f[N][N];
int main(){
    cin>>n>>m>>k;
    memset(f,0x3f,sizeof f);
    f[0][0]=0;
    for(int i=0;i<k;i++){
        int a,b,c;
        cin>>a>>b>>c;
        for(int j=n;j>=0;j--){
            for(int z=m;z>=0;z--){
                f[j][z]=min(f[j][z],f[max(0,j-a)][max(0,z-b)]+c);
            }
        }
    }
    cout<<f[n][m];
}
//注:平常二维费用是背包就那些容量,超过装不下,就要放弃,这题是超过也无所谓,大于等于就行
//所以在a>j以及b>z的时候是满足条件的,所以这些状态要计算,但是数组[][]里不能是负啊,所以
//就可以理解为这个物品(缸)已经满足了,前面i-1的物品不需要再选了,也就是不用提供j-a或z-b了
//所以前面的部分就可以用f[0][0]表示,意思就是前i-1的物品提供了0氮气0氧气
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 612. 球的体积

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sy=new Scanner(System.in);
        int r;
        r=sy.nextInt();
        System.out.printf("VOLUME = %.3f",(4/3.0)*3.14159*r*r*r);
    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~