首页 > 代码库 > cf428c 模拟题

cf428c 模拟题

2024-07-02 00:27:39   224人阅读

这题说的是给了 n个数然后又 k次 的交换任意位置的 数字的机会  计算最长的连续子序列的和

 这要撸  模拟整个 过程 并不能就是算最长的递增序列 如果只是 找最长的 和序列的 话 会存在 很多问题 在替换的时候 每一个决策 都影响着 下一个决策  这样 存在谁与谁替换 这样的状态有 200！种    那就枚举每个区间这样就可以使得 我们所用替换方法得当  因为在替换中我们进行替换是对不同区间的 操作 比如 在替换序列之内的 数字的时候 其实操作的就是不同的区间 与外面的序列进行替换的时候 操作的 是不同的 区间 这样就可以 可以知道 每个区间都是有可能成为 最大区间的

#include <iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
struct inq{
  int x;
  inq(int a=0){ x=a;  }
  bool operator <(const inq &A)const {
    return x>A.x;
  }
};
struct outq{
   int x;
   outq(int a=0){ x=a;  }
   bool operator <(const outq &A)const{
     return x<A.x;
   }
};
priority_queue<inq>In;
priority_queue<outq>Out;
int d[250],mav,GH,sum,k,n;
void jud(){
    int num=k;
    while(num){
        bool falg=true;
        int id=0,od=0,mi,mo;
        if(In.size()!=1){
            id=1;  mi=In.top().x;
        }
        if(!Out.empty()){
            od=1; mo=Out.top().x;
        }
        if(id&&od&&mi<0&&mo>0){
             falg=false;
            sum+=mo-mi;  In.pop();  Out.pop();
        }
        else if(id&&mi<0){
            falg=false;
            sum+=-mi; In.pop();
        }
        else if(od&&mo>0){
            falg=false;
            sum+=mo; Out.pop();

        }else if(od&&id&&mo>mi){falg=false;
            sum+=mo-mi;  Out.pop(); In.pop();
        }
        --num;
        if(falg) break;
    }
    mav=sum>mav?sum:mav;
}
int main()
{
    mav=-3000000;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;++i)
        scanf("%d",&d[i]);
    for(int L=0;L<=n;L++){
        for(int S=0;S+L<n;++S){
                sum=0;
            for(int j=0;j<n;j++)
            if(j>=S&&j<=L+S) { sum+=d[j];In.push(d[j]);   }
            else Out.push(d[j]);
            jud();
            while(!In.empty()) In.pop();
            while(!Out.empty()) Out.pop();
        }

    }
    printf("%d\n",mav);
    return 0;
}
View Code

 


联系
我们