头像

QingQingDE




离线:3天前


最近来访(54)
用户头像
acwing_0239
用户头像
有恒
用户头像
天堂已经死了
用户头像
1900qingqing
用户头像
用户头像
北港城
用户头像
星逐月丶
用户头像
知初
用户头像
kunmy
用户头像
itdef
用户头像
蓬蒿人
用户头像
yxc
用户头像
swaga


AcWing《Linux基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/57/group_buy/34144/



新鲜事 原文

AcWing《Linux基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/57/group_buy/34144/



#include<iostream>
#include<algorithm>

using namespace std;

const int N = 55;

int n;
int ans;//记录总最少序列的个数
int a[N]; 
int up[N];//记录每个上升序列的结尾的数
int down[N];//记录每个下降序列的结尾的数

void dfs(int z, int u, int d){//z表示目前遍历到的序列元素序号, u表示上升序列的数量,d表示下降序列的数量 
    if(u + d >= ans) return;//如果上升和下降序列和已经大于或等于最小序列数,就不可能再产生更少的序列数,直接退出即可
    if(z == n){//如果已经遍历到这个样例的最后一个数,就可以返回的答案了 
        ans = u + d;
        return ;
    } 

    //上升序列 
    int k = 0;//k表示目前遍历到的序列总数
    while(k < u && up[k] >= a[z]) k ++ ;//如果当前上升序列的最后一个数大于等于当前遍历到的元素,就继续往后遍历下一个上升序列
    int t = up[k];//记录结尾元素,用于恢复现场
    up[k] = a[z];//遍历到合适的上升序列后,就将当前元素加入到上升序列的结尾
    if(k < u) dfs(z + 1, u, d);//如果k小于u,表示当前还没有遍历到最后的空的上升序列,所以就不用新加上升序列,所以上升序列的个数不变,加入原始序列的新的需要遍历的元素,开始新的遍历
    else dfs(z + 1, u + 1, d);//如过k = u,表示当前遍历的元素已经加入到最后的空的上升序列中,这时需要新建立一个上升序列,所以u + 1
    up[k] = t;//恢复现场 

    //下降序列 
    k = 0;  
    while(k < d && down[k] <= a[z]) k ++ ;//如果当前下降序列的最后一个数大于等于当前遍历到的元素,就继续往后遍历下一个上升序列
    t = down[k];
    down[k] = a[z];
    if(k < d) dfs(z + 1, u, d);//与上述上升序列同理 
    else dfs(z + 1, u , d + 1);//与上述上升序列同理
    down[k] = t; 
} 

int main()
{
    while(cin>>n, n){
        for(int i = 0; i < n; i ++ ) cin>>a[i];

        ans = n;//将最大序列数设为元素数,即给dfs设置边界

        dfs(0, 0, 0);//刚开始所有序列的数量都是0

        cout<<ans<<endl; 
    }
    return 0;
}


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

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 55;

int n;
int ans;//记录总最少序列的个数
int a[N]; 
int up[N];//记录每个上升序列的结尾的数
int down[N];//记录每个下降序列的结尾的数

void dfs(int z, int u, int d){//z表示目前遍历到的序列元素序号, u表示上升序列的数量,d表示下降序列的数量 
    if(u + d >= ans) return;//如果上升和下降序列和已经大于或等于最小序列数,就不可能再产生更少的序列数,直接退出即可
    if(z == n){//如果已经遍历到这个样例的最后一个数,就可以返回的答案了 
        ans = u + d;
        return ;
    } 

    //上升序列 
    int k = 0;//k表示目前遍历到的序列总数
    while(k < u && up[k] >= a[z]) k ++ ;//如果当前上升序列的最后一个数大于等于当前遍历到的元素,就继续往后遍历下一个上升序列
    int t = up[k];//记录结尾元素,用于恢复现场
    up[k] = a[z];//遍历到合适的上升序列后,就将当前元素加入到上升序列的结尾
    if(k < u) dfs(z + 1, u, d);//如果k小于u,表示当前还没有遍历到最后的空的上升序列,所以就不用新加上升序列,所以上升序列的个数不变,加入原始序列的新的需要遍历的元素,开始新的遍历
    else dfs(z + 1, u + 1, d);//如过k = u,表示当前遍历的元素已经加入到最后的空的上升序列中,这时需要新建立一个上升序列,所以u + 1
    up[k] = t;//恢复现场 

    //下降序列 
    k = 0;  
    while(k < d && down[k] <= a[z]) k ++ ;//如果当前下降序列的最后一个数大于等于当前遍历到的元素,就继续往后遍历下一个上升序列
    t = down[k];
    down[k] = a[z];
    if(k < d) dfs(z + 1, u, d);//与上述上升序列同理 
    else dfs(z + 1, u , d + 1);//与上述上升序列同理
    down[k] = t; 
} 

int main()
{
    while(cin>>n, n){
        for(int i = 0; i < n; i ++ ) cin>>a[i];

        ans = n;//将最大序列数设为元素数,即给dfs设置边界

        dfs(0, 0, 0);//刚开始所有序列的数量都是0

        cout<<ans<<endl; 
    }
    return 0;
}



C++ 代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

int a[N];
int f[N];//f[i]储存以i结尾的不下降子序列的长度 
int g[N];//g[i]储存第i个序列的结尾元素
int n;

int main()
{
    while(cin>>a[n]) n ++ ;

    int res = 0, cbt = 0;

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

        int k = 0;//k代表从目前已经建立的第一个序列开始遍历每个序列的结尾值 
        while(k < cbt && a[i] > g[k]) k ++ ;//当目前遍历到的序列的结尾值不大于新遍历的元素时,序列序号++ 
        if(k == cbt) g[cbt ++ ] = a[i];//因为cbt是后++,所以实际上当k==cbt时,代表目前所有存数的序列的结尾数都大于等于a[i],所以就将a[i]加到空的序列的结尾,并再开一个空序列 
        else g[k] = a[i];//如果没有遍历到最后一个序列,就代表有某个序列的结尾大于a[i],此时直接将a[i]加到这个序列的结尾 
    }
    cout<<res<<endl;
    cout<<cbt<<endl;
    return 0;
} 


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

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

int a[N];
int f[N];//f[i]储存以i结尾的不下降子序列的长度 
int g[N];//g[i]储存第i个序列的结尾元素
int n;

int main()
{
    while(cin>>a[n]) n ++ ;

    int res = 0, cbt = 0;

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

        int k = 0;//k代表从目前已经建立的第一个序列开始遍历每个序列的结尾值 
        while(k < cbt && a[i] > g[k]) k ++ ;//当目前遍历到的序列的结尾值不大于新遍历的元素时,序列序号++ 
        if(k == cbt) g[cbt ++ ] = a[i];//因为cbt是后++,所以实际上当k==cbt时,代表目前所有存数的序列的结尾数都大于等于a[i],所以就将a[i]加到空的序列的结尾,并再开一个空序列 
        else g[k] = a[i];//如果没有遍历到最后一个序列,就代表有某个序列的结尾大于a[i],此时直接将a[i]加到这个序列的结尾 
    }
    cout<<res<<endl;
    cout<<cbt<<endl;
    return 0;
} 



QingQingDE
1个月前
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

int a[N], f[N];
int n;

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

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



QingQingDE
1个月前
#include<iostream>
#include<cstring>

using namespace std;

const int N = 110;

int n;
int f[N];
int a[N];

int main()
{
    cin>>n;
    while(n -- ){
        int m;
        cin>>m;
        int res = 0;
        for(int i = 0; i < m; i ++ ){
            cin>>a[i];
        }
        for(int i = 0; i < m; i ++ ){
            f[i] = 1;
            for(int j = 0; j < i; j ++ ){
                if(a[j] > a[i]){
                    f[i] = max(f[i], f[j] + 1);
                }
                res = max(res, f[i]);
            }
        }
        memset(f, 0, sizeof f);
        for(int i = m - 1; i >= 0; i -- ){
            f[i] = 1;
            for(int j = m - 1; j > i; j -- ){
                if(a[j] > a[i]){
                    f[i] = max(f[i], f[j] + 1);
                }
                res = max(res, f[i]);
            }
        }
        cout<<res<<endl;
    }
    return 0;
}


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

QingQingDE
1个月前
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 1e4 + 10;

typedef pair<int, int>PII;

int f[N];
int n;

int main()
{
    cin>>n;
    PII a[N];
    for(int i = 0; i < n; i ++ ){
        cin>>a[i].first>>a[i].second;
    }

    sort(a, a + n);
    int res = 0;
    for(int i = 0; i < n; i ++ ){
        f[i] = 1;
        for(int j = 0; j < i; j ++ ){
            if(a[i].second > a[j].second){
                f[i] = max(f[i], f[j] + 1);
            } 
        }
        res = max(f[i], res);
    }
    cout<<res<<endl;
    return 0;
}



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

QingQingDE
1个月前
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1004;

int n;
int f[N];
int g[N];
int a[N];

int main()
{
    cin>>n;
    for(int i = 0; i < n; i ++ ){
        cin>>a[i];
    }

    for(int i = 0; i < n; i ++ ){
        f[i] = 1;
        for(int j = 0; j < i; j ++ ){
            if(a[i] > a[j]){
                f[i] = max(f[i], f[j] + 1);//从左往右遍历,找出从左向右的不下降子序列 
            }
        } 
    }

    for(int i = n - 1; i >= 0; i -- ){
        g[i] = 1;
        for(int j = n - 1; j > i; j -- ){
            if(a[i] > a[j]){
                g[i] = max(g[i], g[j] + 1);//从右往左遍历,找出从右向左的不下降子序列 
            }
        }
    }

    int res = 0;
    for(int i = 0; i < n; i ++ ){
        res = max(res, f[i] + g[i] - 1);//遍历找出每个点最长的坡形序列的长度,因为中间那个点被计算了两次,所以要减一 
    }
    cout<<n - res<<endl;;
    return 0;
}