头像

钟跃民

THE CCP




离线:13小时前


活动打卡代码 AcWing 786. 第k个数

钟跃民
16小时前
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,k;
int q[N];
int quick_sort(int l,int r,int k){
    if(l==r) return q[l];
    int x=q[l] , i=l-1,j=r+1;
    while(i<j){
        while(q[++i]<x);
        while(q[--j]>x);
        if(i<j) swap(q[i],q[j]);
    }
    int s1=j-l+1;
    if(k<=s1) return quick_sort(l,j,k);
    return quick_sort(j+1,r,k-s1);
}
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>q[i];
    cout<<quick_sort(0,n-1,k)<<endl;
    return 0;
}



活动打卡代码 AcWing 282. 石子合并

#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int a[N],s[N];
int f[N][N];
int n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]+=s[i-1]+a[i];
    } 
    for(int len=1;len<n;len++){
        for(int i=1;i+len<=n;i++){
            int j=i+len;
            f[i][j]=1e8;
            for(int k=i;k<=j-1;k++){
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
            }
        }
    }
    cout<<f[1][n];
    return 0;
}



#include <bits/stdc++.h>
using namespace std;
string a,b;
const int N = 1010;
int f[N][N];
int n,m;
int main(){
    cin>>n>>m;
    cin>>a>>b;
    a="1"+a;
    b="2"+b;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);
        }
    }
    cout<<f[n][m];
    return 0;
}




#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
int a[N],f[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        f[i]=1;
        for(int j=1;j<i;j++)
            if(a[i]>a[j]) f[i]=max(f[i],f[j]+1);
    }
    int res=0;
    for(int i=1;i<=n;i++)
        res=max(res,f[i]);
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 898. 数字三角形

#include <bits/stdc++.h>
using namespace std;
const int N = 510 , INF = 1e9;
int n;
int a[N][N],f[N][N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin>>a[i][j];
    for(int i=0;i<=n;i++)
        for(int j=0;j<=i+1;j++)
            f[i][j]=-INF;
    f[1][1]=a[1][1];
    for(int i=2;i<=n;i++)
        for(int j=1;j<=i;j++)
            f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];
    int res=-INF;
    for(int i=1;i<=n;i++)
        if(f[n][i]>res) res=f[n][i];
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 9. 分组背包问题

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

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


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

#include <bits/stdc++.h>
using namespace std;
const int N=25000,M=2010;
int n,m;
int v[N],w[N];
int f[N];
int main(){
    cin>>n>>m;
    int cnt=0;
    for(int i=1;i<=n;i++){
        int a,b,s;
        cin>>a>>b>>s;
        int k=1;
        while(k<=s){
            cnt++;
            v[cnt]=a*k;
            w[cnt]=b*k;
            s-=k;
            k*=2;
        }
        if(s>0){
            cnt++;
            v[cnt]=a*s;
            w[cnt]=b*s;
        }
    }
    n=cnt;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];
    return 0;
}



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

#include <bits/stdc++.h>
using namespace std;
const int N =110;
int n,m;
int v[N],w[N],s[N];
int f[N][N];
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=1;j<=m;j++)
            for(int k=0;k*v[i]<=j&&k<=s[i];k++)
                f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
    cout<<f[n][m];
    return 0;
}


活动打卡代码 AcWing 3. 完全背包问题

#include <bits/stdc++.h>
using namespace std;
const int N =1010;
int n,m;
int v[N],w[N];
int f[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int j=v[i];j<=m;j++){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];
    return 0;
}


活动打卡代码 AcWing 2. 01背包问题

#include <bits/stdc++.h> using namespace std; const int N =1010; int n,m; int v[N],w[N],f[N]; int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>v[i]>>w[i]; for(int i=1;i<=n;i++){ for(int j=m;j>=v[i];j--){ f[j]=max(f[j],f[j-v[i]]+w[i]); } } cout<<f[m]; return 0; }