头像

月息




离线:27分钟前


最近来访(32)
用户头像
.凌桓
用户头像
一个人的巴黎
用户头像
2010
用户头像
白也_y
用户头像
incra
用户头像
大伟老师的亲传弟子
用户头像
Andy2035

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

月息
1天前
#include <iostream>
using namespace std;
const int N=1e5+10;
int n;
int x;
int f[N][2];
int main(){
    cin>>n;
    cin>>x;
    f[0][0]=0;
    f[1][0]=0;
    f[1][1]=-x;
    f[0][1]=0xcf;
    for(int i=2;i<=n;i++){
        cin>>x;
        f[i][0]=max(f[i-1][0],f[i-1][1]+x);
        f[i][1]=max(f[i-2][0]-x,f[i-1][1]);
       // cout<<f[i][0]<<" " <<f[i][1]<<endl;
    }
    cout<<f[n][0];
}


活动打卡代码 AcWing 4804. 构造矩阵

月息
2天前
#include <iostream>
using namespace std;
int n,m;

const int N=110;
int b[N][N];
int a[N][N];

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
           cin>>b[i][j];
           a[i][j]=1;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>b[i][j];
            if(b[i][j]==0){
                for(int k=0;k<m;k++){
                    a[i][k]=0;
                }
                for(int k=0;k<n;k++){
                    a[k][j]=0;
                }
            }
        }
    }
    int ant=1;

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
             int sum=0;
            if(b[i][j]){
                for(int k=0;k<m;k++){
                    sum+=a[i][k];
                }
                for(int k=0;k<n;k++){
                    sum+=a[k][j];
                }
                if(sum==0){
                    ant=0;
                }
            }
        }
    }
    if(ant){
        cout<<"YES"<<endl;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cout<<a[i][j]<<" ";
            }
            cout<<endl;
        }
    }else{
        cout<<"NO"<<endl;
    }

    return 0;
}


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

月息
2天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n,k;
const int N=1e5+10;
int f[N][110][2];
int a[N];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
     memset(f,0xcf,sizeof f);//f[0][0][1]不存在定义为-inf
     for(int i=0;i<=n;i++)f[i][0][0]=0;//从零开始没有买没有交易为0
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+a[i]);
            f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-a[i]);
        }
    }
    int res=0;
    for(int i=1;i<=k;i++)res=max(res,f[n][i][0]);
    cout<<res<<endl;
    return 0;
}


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

月息
4天前
#include <iostream>
using namespace std;
int T;
int n;
int w;
const int N=1e5+10;
int f[N];
int main(){
    cin>>T;
    while(T--){
        int a;//数组?累赘罢了
        cin>>n;
        for(int i=2;i<=n+1;i++){
            cin>>a;
            f[i]=max(f[i-1],f[i-2]+a);
        }
        cout<<f[n+1]<<endl;
    }

    return 0;
}



月息
5天前
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define v first  
#define w second

using namespace std;
typedef pair<int,int> PII;
const int N=32010,M=70;
int n,m;
vector<PII> son[M];
PII fa[M];
int f[M][N];
int main(){
    cin>>n>>m;
     int v,p,q;
    for(int i=1;i<=m;i++){
         cin>>v>>p>>q;
         if(!q)fa[i]={v,v*p};
         else son[q].push_back({v,v*p});
    }
    for(int i=1;i<=m;i++){//在第i组在j体积下已经选择第i主件的最大值
        if(fa[i].v){
            for(int j=fa[i].v;j<=n;j++){
                f[i][j]=f[i-1][j-fa[i].v]+fa[i].w;//更新当前第i组的状态(因为从后往前所有不需要用max更新)
            }
            for(int k=0;k<son[i].size();k++){
                for(int j=n;j>=son[i][k].v;j--){
                    if(f[i][j-son[i][k].v]>0){
                        f[i][j]=max(f[i][j],f[i][j-son[i][k].v]+son[i][k].w);//在附件中选择一个最优
                    }
                }
            }
        }
        for(int j=0;j<=n;j++)
        f[i][j]=max(f[i][j],f[i-1][j]);//不是主件则将上一组主件更新

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



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

月息
7天前
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=110,M=10010;
int T;
int f[M];
struct Stone{
    int s,e,l;
    bool operator<(const Stone&x)const{
        return s*x.l<l*x.s;
    }
}stones[N];
int n;
int main(){
    cin>>T;
    int cnt=0;
    while(T--){
        cnt++;
      cin>>n;
      memset(f, 0xcf, sizeof f);
     f[0]=0;
      int sum_s=0;
      for(int i=1;i<=n;i++){
          int s,e,l;
          cin>>s>>e>>l;
          stones[i]={s,e,l};
          sum_s+=s;
      }
      sort(stones+1,stones+n+1);
      for(int i=1;i<=n;i++){
          int s=stones[i].s;
          int e=stones[i].e;
          int l=stones[i].l;
          for(int j=sum_s;j>=stones[i].s;j--){

              f[j]=max(f[j],f[j-s]+max(0,e-l*(j-s)));
          }
      } 
      int ans=0;
      for(int i=1;i<=sum_s;i++){
          ans=max(ans,f[i]);
      }
      cout<<"Case #"<<cnt<<": "<<ans<<endl;;
    }
    return 0;
}



月息
11天前
#include <iostream>
using namespace std;
const int N=1010;
int f[N][N];
int v[N],w[N];
int n,m;
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=1;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]);
            }            
        }
    }
    for(int i=1,j=m;i<=n;i++){

        if(j>=v[i]&&f[i][j]==f[i+1][j-v[i]]+w[i]){
            cout<<i<<" ";
            j-=v[i];
        }
    }
    return 0;
}




月息
11天前
#include<iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=110;
int n,m;
int e[N],ne[N],h[N],idx;
int v[N],w[N],f[N][N];
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(e[i]);
        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;
     int p;
    for(int i=1;i<=n;i++){

        cin>>v[i]>>w[i]>>p;
        if(p==-1)root=i;
        else add(p,i);
    }
    dfs(root);
    cout<<f[root][m]<<endl;
    return 0;
}



月息
13天前
#include<iostream>
using namespace std;
const int N=1010;
int f[N];
int g[N];
int n,m;
int mod=1e9+7;
int main(){
    cin>>n>>m;
    int v,w;
    f[0]=0;
    for(int i=0;i<=m;i++)g[i]=1;
    for(int i=1;i<=n;i++){
        cin>>v>>w;
        for(int j=m;j>=v;j--){
            int maxv=max(f[j],f[j-v]+w);
            int s=0;
            if(maxv==f[j])s+=g[j];
            if(maxv==f[j-v]+w)s=(s+g[j-v])%mod;
            g[j]=s;
            f[j]=maxv;
        }
    }
    cout<<g[m]<<endl;
    return 0;
}


新鲜事 原文

月息
14天前
AcWing《Django框架课》拼团优惠!https://www.acwing.com/activity/content/introduction/72/group_buy/118930/