头像

vlehr




在线 


活动打卡代码 AcWing 1068. 环形石子合并

vlehr
6个月前
#include <bits/stdc++.h>

using namespace std;

const int maxn = 410, inf = 0x3f3f3f3f;

int w[maxn],sum[maxn];
int f[maxn][maxn],g[maxn][maxn];

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
        w[i+n] = w[i];
    }

    for(int i=1;i<=n*2;i++) sum[i]+=sum[i-1]+w[i];

    memset(f, 0x3f, sizeof f);
    memset(g, -0x3f, sizeof g);

    for(int len=1; len<=n; len++){
        for(int l=1;l+len-1<=n*2;l++){
            int r = l+len-1;
            if(len == 1){
                f[l][r] = g[l][r] = 0;
            }
            else{
                for(int k=l;k<r;k++){
                    f[l][r] = min(f[l][r], f[l][k]+f[k+1][r]+sum[r]-sum[l-1]);
                    g[l][r] = max(g[l][r], g[l][k]+g[k+1][r]+sum[r]-sum[l-1]);
                }
            }
        }
    }
    int mi = inf, mx = -inf;

    for(int i=1;i<=n;i++){
        mi = min(mi, f[i][i+n-1]);
        mx = max(mx, g[i][i+n-1]);
    }
    printf("%d\n%d\n",mi,mx);
    return 0;

}


活动打卡代码 AcWing 300. 任务安排1

vlehr
6个月前
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5010;
const int inf = 0x3f3f3f3f;

int sumc[maxn],sumt[maxn];
int f[maxn];

int main(){
    int n,s;
    scanf("%d%d",&n,&s);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&sumt[i],&sumc[i]);
        sumt[i]+=sumt[i-1];
        sumc[i]+=sumc[i-1];
    }
    f[0]=0;

    for(int i=1;i<=n;i++){
        f[i] = inf;
        for(int j=0;j<i;j++){
            f[i] = min(f[i],f[j]+(sumc[i]-sumc[j])*sumt[i]+s*(sumc[n]-sumc[j]));
        }
    }
    printf("%d\n",f[n]);
    return 0;
}


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

vlehr
6个月前
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+5;

int f[maxn][2],nums[maxn];

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)   scanf("%d",nums+i);
        f[1][1]=nums[1];
        f[1][0]=0;

        for(int i=2;i<=n;i++){
            f[i][1]=f[i-1][0] + nums[i];
            f[i][0]=max(f[i-1][1],f[i-1][0]);
        }

        printf("%d\n",max(f[n][1],f[n][0]));
    }
    return 0;
}


活动打卡代码 AcWing 906. 区间分组

vlehr
6个月前

按左端点排序,保存所有组中的最右端点的最小值,扫描的时候判断当前区间能否加到该最小值的后边,如果可以,则更新最小的最右端点。否则开新组。

为什么可以直接接在最小的最右端点。假如在已经分好的组里面的最小r1和次小r2,按顺序有两个新的区间l1,l2要加进来,以上策略不正确的情况只有在l1可以加入r1和r2,而本来l2可以加入r1的,但是因为l1占了r1,以至于l2两个都加不进来,导致要开新组。
但是这种情况是不存在的。这是因为l2>=l1,l1能加入的组l2一定都能加入,所以l1加入的组无所谓,那就每次加入最小即可,这样便于维护。

#include <bits/stdc++.h>

using namespace std;

struct node{
    int l,r;
    bool operator < (const node& b)const{
        if(l<b.l)   return true;
        else if(l == b.l)   return r<b.r;
        else return false;
    }
};


const int maxn = 1e5+5;
node intv[maxn];

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)   scanf("%d%d",&intv[i].l,&intv[i].r);

    sort(intv+1, intv+n+1);

    int cnt=1,leftmost = intv[1].r;

    priority_queue<int, vector<int>, greater<int> >que;
    que.push(leftmost);
    for(int i=2;i<=n;i++){
        if(intv[i].l>que.top()){
            que.pop();
        }
        else{
            cnt++;
        }
        que.push(intv[i].r);
    }

    printf("%d\n",cnt);
    return 0;
}


活动打卡代码 AcWing 125. 耍杂技的牛

vlehr
6个月前
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e4+4;
typedef long long ll;

struct node{
    ll w,s;
    bool operator < (const node &b)const{
        return (w+s)<(b.w+b.s);
    }
};

node cow[maxn];
ll sum[maxn];

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&cow[i].w,&cow[i].s);
    }

    sort(cow+1, cow+n+1);

    for(int i=1;i<=n;i++)   sum[i]+=cow[i].w+sum[i-1];

    ll res = -0x3f3f3f3f3f3f3f3f;

    for(int i=1;i<=n;i++){
        res = max(res,sum[i-1]-cow[i].s);
    }
    printf("%lld\n",res);
    return 0;

}



活动打卡代码 AcWing 104. 货仓选址

vlehr
6个月前
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+5;

int nums[maxn];

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&nums[i]);
    }

    sort(nums+1,nums+1+n);

    for(int i=1;i<=n;i++)   nums[i]+=nums[i-1];

    int res=0x3f3f3f3f;

    for(int i=1;i<=n;i++){
        int x = nums[i]-nums[i-1];
        res = min(res, nums[n]-nums[i]*2+(2*i-n)*x);
    }
    printf("%d\n",res);
    return 0;

}



vlehr
6个月前
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+5;

struct node{
    int l,r;
    bool operator < (const node & b)const{
        if(r<b.r)   return true;
        else if(r==b.r) return l<b.l;
        else return false;
    }
};

node intv[maxn];

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)   scanf("%d%d",&intv[i].l,&intv[i].r);

    sort(intv+1,intv+n+1);

    int cnt=1,leftmost=intv[1].r;

    int i=2;
    while(i<=n){
        while(i<=n && intv[i].l <= leftmost){
            i++;
        }
        if(i>n) break;
        cnt++;
        leftmost = intv[i].r;
    }
    printf("%d\n",cnt);
    return 0;
}



活动打卡代码 AcWing 905. 区间选点

vlehr
6个月前
#include <bits/stdc++.h>

using namespace std;

struct node{
    int l,r;
    bool operator < (const node &b)const{
        if(r < b.r )    return true;
        else if(r==b.r){
            return l<b.l;
        }
        else return false;
    }
};

const int maxn = 1e5+5;
node intv[maxn];

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&intv[i].l,&intv[i].r);
    }

    sort(intv+1,intv+n+1);


    int cnt = 1;
    int leftmost = intv[1].r;
    int i=2;
    while(i<=n){
        while(i<=n && intv[i].l<=leftmost){
            i++;
        } 
        if(i>n) break;
        leftmost = intv[i].r;
        cnt++;
    }
    printf("%d\n",cnt);
    return 0;
}


活动打卡代码 AcWing 135. 最大子序和

vlehr
7个月前
#include <bits/stdc++.h>

using namespace std;

const int maxn = 3e5+5;

int que[maxn],sum[maxn];

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i <= n; i++){
        scanf("%d",&sum[i]);
        sum[i] += sum[i-1];
    }
    int head=0, rear = 0, res = -0x3f3f3f3f;
    for(int i = 1; i <= n; i++){
        if(que[head] + m < i)   head++;
        res = max(res, sum[i] - sum[que[head]]);
        while(head<=rear && sum[i] <= sum[que[rear]]) rear--;
        que[++rear] = i;
    }
    printf("%d\n",res);
    return 0;
}


活动打卡代码 AcWing 187. 导弹防御系统

vlehr
7个月前
#include <bits/stdc++.h>

using namespace std;

const int maxn = 55;

int up[maxn],down[maxn],nums[maxn];
int ans,n;

void dfs(int pos,int su,int sd){
    if(sd+su>=ans)  return;
    if(pos>=n){
        ans = sd + su;
        return;
    }

    int k=0;
    while(k<su && up[k] <= nums[pos]) k++;
    int t=up[k];
    up[k] = nums[pos];
    if(k>=su) dfs(pos + 1, su + 1, sd);
    else dfs(pos + 1, su, sd);
    up[k]=t;

    k=0;
    while(k<sd && down[k] >= nums[pos]) k++;
    t = down[k];
    down[k] = nums[pos];
    if(k >= sd) dfs(pos+1, su, sd+1);
    else dfs(pos+1, su, sd);
    down[k] = t;
}

int main(){
    while(cin>>n,n){
        for(int i=0;i<n;i++)    cin>>nums[i];
        ans=n;
        dfs(0,0,0);
        cout<<ans<<endl;
    }
    return 0;
}