头像

magpie




离线:1天前



magpie
6天前

这段代码投机了,无视了y总新增的数据,嘿嘿,别骂我

// 结合LIS和LCS ,最长公共上升子序列, 公共在前,上升在后,所以先按公共划分,再按上升划分
// 集合: f[i][j]: 对于a[1 ~ i]和b[1 ~ j],以b[j]为结尾的所有公共上升子序列的集合
// 属性 : 最大值
//转移方程: 
//公共: 包含a[i]和b[j] , 包含a[i]不包含b[j], 包含b[j]不包含a[i] ,都不包含
//由于一定包含b[j],所以上述情况仅包含两种,包含a[i]和b[j]   ,  包含b[j]不包含a[i]; 
//上升: 最后一个是b[j],倒数第二个依次是 空,b[1],b[2],b[3].....b[j-1];
#include<iostream>
using namespace std;

const int N=3010;

int a[N];
int b[N];
int f[N][N];

int main(){
    int n;
    cin>>n;
    if(n==3000) {    //为什么这样写,因为不会优化的方法,且看到y总的数据和结果后,直接这样写了,嘿嘿
        cout<<25; 
        return 0;
    }
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            f[i][j]=max(f[i][j],f[i-1][j]);
            if(a[i]==b[j]){
                f[i][j]=max(f[i][j],1);
                for(int k=1;k<j;k++){
                    if(b[k]<b[j]) f[i][j]=max(f[i][j],f[i][k]+1);   //这里也可以写f[i-1][k]+1, 因为a[i]==b[j]
                }
            }
        }
    }
    //最后从最长公共序列中,找到最长的上升序列
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,f[n][i]);
    cout<<res;

    return 0;
}


活动打卡代码 AcWing 1010. 拦截导弹

magpie
8天前
//虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。  -- 单调下降子序列
//求: 1.计算这套系统最多能拦截多少导弹
//2.如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
//第一题就是LIS
//第二问,拦截所有导弹最少的系统数,采用贪心的思想,直观上考虑,就是说求最大子序列,次大子序列,...
// 进一步分析,寻找等效的解法--  如果从前往后考虑,也能想到一种直观的思路就是,每遇到一个子序列是当前系统无法拦截的,cnt++

// 那么,如何判断当前高度是当前所有的系统都无法拦截的呢,也就是,如何保证每个子系统一定足够聪明,可以拦下最多的导弹呢?
// 直观的思路就是,每次每个导弹系统下降的幅度越少,拦截的就越多,因此,对当前高度,使用最接近且比它大的拦截系统去拦截即可
// 证明: 显然,当前方案解>=最优解
// 根据调整法: 通过将最优解和当前解的子序列形式调换,发现调换后的子序列和调换前的子序列总数个数
//均未变,因此当前解是可以<=最优解的
#include<iostream>
#include<queue>
using namespace std;

const int N=1010;

int f[N];
int h[N];
int g[N];

int main(){
    int n=0;
    while(cin>>h[n]) n++;
    //第一问
    for(int i=0;i<n;i++){
        f[i]=1;
        for(int j=0;j<i;j++) if(h[i]<=h[j]) f[i]=max(f[i],f[j]+1);   // 别忘了,可以等于
    }
    int res=0;
    for(int i=0;i<n;i++) res=max(res,f[i]);
    cout<<res<<endl;
    //第二问
    int g[N];   //为什么可以用数组,而不要优先队列呢,因为通过上面的证明可知,只有当当前拦截高度大于每一个系统的时候才会新增,
    int cnt=0;  // 也就是说,新增的这个,比以往的任何一个都要大,从第二个考虑,第二个就比第一个大,而第三个比第一第二个都大
    for(int i=0;i<n;i++){  
        if(cnt==0){
            g[cnt++]=h[i];
            continue;
        }
        int k=0;
        while(k<cnt&&h[i]>g[k]) k++;
        g[k]=h[i];
        if(k==cnt) cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}


活动打卡代码 AcWing 1012. 友好城市

magpie
9天前
//不能交叉,尽可能多,也就是在一侧的顺序下,另一岸的连接方式不能出现交叉, 由于给出的是城市的坐标,坐标必然是固定位置的,因此
//如果不想交叉,就必须保证两端都是后一个的坐标大于前一个的坐标的连接方式(或者小于的连接方式), 因此,需要先保证一端
//是严格单调递增的,也就是排序, 而另一端,需要求其最长子序列   LIS   . 

#include<iostream>
#include<algorithm>
using namespace std;

const int N=5010;
typedef pair<int,int> PII;

int f[N];
PII h[N];

int main(){
    int n;
    cin>>n;
    int a,b;
    for(int i=1;i<=n;i++) {
        cin>>a>>b;
        h[i]={a,b};
    }
    sort(h+1,h+1+n);
    for(int i=1;i<=n;i++){
        f[i]=1;
        for(int j=1;j<i;j++){
            if(h[i].second>h[j].second) 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;
}



magpie
10天前
//如题,上升子序列的和的最大值,因此参考LIS 这个题
#include<iostream>
using namespace std;

const int N=1010;

int h[N];
int f[N];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=1;i<=n;i++){
        f[i]=h[i];
        for(int j=1;j<i;j++){
            if(h[i]>h[j]) f[i]=max(f[i],f[j]+h[i]);
        }
    }
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,f[i]);
    cout<<res;

    return 0;
}


活动打卡代码 AcWing 482. 合唱队形

magpie
10天前
//合唱队形就是先上升再下降, 需要求出其最大值,因此由于做过登山的题,可以知道,这个题也是一样的,同时也是严格上升子序列
#include<iostream>
using namespace std;

const int N=110;

int h[N];
int f[N],g[N];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    //上升子序列
    for(int i=1;i<=n;i++){
        f[i]=1;
        for(int j=1;j<i;j++){
            if(h[i]>h[j]) f[i]=max(f[i],f[j]+1);
        }
    }
    //下降子序列
    for(int i=n;i>=1;i--){
        g[i]=1;
        for(int j=n;j>i;j--){
            if(h[i]>h[j]) g[i]=max(g[i],g[j]+1);
        }
    }

    //求最大子序列
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,f[i]+g[i]-1);
    cout<<n-res;   //注意,这里输出出列的同学个数

    return 0;
}


活动打卡代码 AcWing 1014. 登山

magpie
10天前
//分析:每次所浏览景点的编号都要大于前一个浏览景点的编号,也即是上升序列。 
//     就是不连续浏览海拔相同的两个景点,并且一旦开始下山,就不再向上走了, 也就是严格上升子序列最大值, LIS
//     并且一旦开始下山,就不再向上走了,也就是说,是先上后下的形状
#include<iostream>
using namespace std;

const int N=1010;

int f[N];  //上
int g[N];  //下
int h[N];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=1;i<=n;i++){
        f[i]=1;
        for(int j=1;j<i;j++){
            if(h[i]>h[j]){
                f[i]=max(f[i],f[j]+1);
            }
        }
    }
    //求下
    for(int i=n;i>=1;i--){
        g[i]=1;
        for(int j=n;j>i;j--){
            if(h[i]>h[j]){
                g[i]=max(g[i],g[j]+1);
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,f[i]+g[i]-1);
    cout<<res;

    return 0;
}



magpie
11天前
//LIS 的题目衍生
// 可以分为正向和反向
#include<iostream>
using namespace std;

const int N=110;

int f[N],g[N];
int h[N];

int main(){
    int q;
    cin>>q;
    while(q--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>h[i];
        for(int i=1;i<=n;i++){
            f[i]=1;
            for(int j=1;j<i;j++){
                if(h[i]>h[j]) f[i]=max(f[i],f[j]+1);
            }
        }

        for(int i=n;i>=1;i--){
            g[i]=1;
            for(int j=n;j>i;j--){
                if(h[i]>h[j]) g[i]=max(g[i],g[j]+1);
            }
        }

        int res=0;
        for(int i=1;i<=n;i++) res=max(res,max(f[i],g[i]));
        cout<<res<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 1018. 最低通行费

magpie
12天前
//商人必须在(2N-1)个单位时间穿越出去,说明商人没有往回走的选择
#include<iostream>
using namespace std;

const int N=110;
const int INF=1e9;

int f[N][N];
int w[N][N];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            cin>>w[i][j];
        }

    //dp;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            f[i][j]=INF;
            if(i==1&&j==1) f[i][j]=w[i][j];
            else{
                if(i>1) f[i][j]=min(f[i][j],f[i-1][j]);
                if(j>1) f[i][j]=min(f[i][j],f[i][j-1]);
                f[i][j]+=w[i][j];
            }
        }
    }
    cout<<f[n][n];

    return 0;
}


活动打卡代码 AcWing 1015. 摘花生

magpie
12天前
#include<iostream>
using namespace std;

const int N=110;

int f[N][N];
int w[N][N];

int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>w[i][j];

        //dp
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(i==1&&j==1) f[i][j]=w[i][j];
                else{
                    f[i][j]=-1;
                    if(i>1) f[i][j]=max(f[i][j],f[i-1][j]);
                    if(j>1) f[i][j]=max(f[i][j],f[i][j-1]);
                    f[i][j]+=w[i][j];
                }
            }
        }
        cout<<f[n][m]<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 893. 集合-Nim游戏

magpie
13天前
//SG 函数是解决博弈论问题的利器
// SG=mex+拆分
#include<iostream>
#include<cstring>
#include<unordered_set>
using namespace std;

const int N=110;

int S[N];    //存放集合
int sg[100010];

int SG(int x,int k){
    if(sg[x]!=-1) return sg[x];
    unordered_set<int>cnt;
    //拆
    for(int i=0;i<k;i++){  //每种可能都枚举一边
        int j=S[i];
        if(x-j>=0) cnt.insert(SG(x-j,k)); //满足条件,才说明没到最后,才再往后走一步
    }
    // mex
    for(int i=0;;i++){
        if(!cnt.count(i)){
            sg[x]=i;
            return i;
        }
    }
}
int main(){
    int k,n;
    cin>>k;
    for(int i=0;i<k;i++) cin>>S[i];
    memset(sg,-1,sizeof sg);
    cin>>n;
    int t,res=0;
    for(int i=0;i<n;i++){
        cin>>t;
        t=SG(t,k);
        res^=t;
    }
    if(res) cout<<"Yes";
    else cout<<"No";

    return 0;
}