头像

西瓜好甜


访客:15952

在线 


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

西瓜好甜
9小时前
//记录全局最小值
#include<bits/stdc++.h>

using namespace std;

const int N = 55;

int n;
int q[N];
//up 表示上升子序列的结尾 
//down 表示下降子序列的结尾
int up[N],down[N];
int ans;
//u表示当前枚举到了第几个数
//su 表示当前上升子序列的个数
//sd 表示当前下降子序列的个数
void dfs(int u,int su,int sd){
    //没有更小
    if(su + sd >= ans) return;
    if(u == n)
    {
        ans = su + sd;
        return;
    }
    //case 1:将当前数字放入上升子序列
    int k = 0;
    while(k < su && up[k] >= q[u]) k ++;

    //需要回溯
    int t = up[k];

    up[k] = q[u];
    if(k < su) dfs(u + 1,su,sd);
    else dfs(u + 1,su + 1,sd);
    up[k] = t;

    //case 2:将当前数字放入下降子序列
    k = 0;
    while(k < sd && down[k] <= q[u]) k ++;
    t = down[k];
    down[k] = q[u];
    if(k < sd) dfs(u + 1,su,sd);
    else dfs(u + 1,su,sd + 1);
    down[k] = t;

}

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

        ans = n;//最坏情况
        dfs(0,0,0);
        cout << ans << endl;
    }    
    return 0;
}


活动打卡代码 LeetCode 59. 螺旋矩阵 II

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n,vector<int>(n));
        vector<vector<bool>> st(n+1,vector<bool>(n+1));
        int dx[] = {0,1,0,-1},dy[]= {1,0,-1,0};
        for(int i = 0,x = 0,y = 0,d = 0;i < n * n;i ++){
            res[x][y] = i + 1;
            st[x][y] = true;
            int a = x + dx[d],b = y + dy[d];
            if(a < 0 || b < 0 || a >= n || b >= n ||st[a][b])
            {
                d = (d + 1) % 4;
                a = x + dx[d],b = y + dy[d];
            }
            x = a,y = b;
        }

        return res;
    }
};


活动打卡代码 LeetCode 57. 插入区间

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& a, vector<int>& b) {
        vector<vector<int>> res;
        int k = 0;
        while(k < a.size() && a[k][1] < b[0]) res.push_back(a[k ++]);

        if(k < a.size()){
            b[0] = min(a[k][0],b[0]);
            while(k < a.size() && b[1] >= a[k][0]){
                b[1] = max(b[1],a[k++][1]);
            }
        }

        res.push_back(b);

        while(k < a.size()) res.push_back(a[k ++]);

        return res;
    }
};


活动打卡代码 LeetCode 56. 合并区间

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& a) {
        vector<vector<int>> res;
        if(a.empty()) return res;
        sort(a.begin(),a.end());
        int l = a[0][0],r = a[0][1];
        for(int i = 1;i < a.size();i ++){
            if(a[i][0] > r){
                res.push_back({l,r});
                l = a[i][0],r = a[i][1];
            }else r = max(r,a[i][1]);
        }
        res.push_back({l,r});
        return res;
    }
};


活动打卡代码 LeetCode 55. 跳跃游戏

class Solution {
public:
    //不存在能跳到前面的跳不到后面 所以只要找跳到的最远的就可以
    bool canJump(vector<int>& nums) {
        for(int i = 0,j = 0;i < nums.size();i ++)
        {
            if(j < i) return false;
            j = max(j,i + nums[i]);
        }
        return true;
    }
};


活动打卡代码 LeetCode 54. 螺旋矩阵

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        int n = matrix.size();
        if(n == 0) return res;
        int m = matrix[0].size();


        int dx[] = {0,1,0,-1},dy[] = {1,0,-1,0};
        vector<vector<bool>> st(n,vector<bool>(m));

        int x = 0,y = 0,d = 0;
        for(int i = 0;i < n * m;i ++){
            res.push_back(matrix[x][y]);
            st[x][y] = true;

            int a = x + dx[d],b = y + dy[d];
            if(a < 0 || a >= n || b < 0 || b >= m || st[a][b]){
                d = (d + 1) % 4;
                a = x + dx[d],b = y + dy[d];
            }
            x = a,y = b;
        }

        return res;

    }
};


活动打卡代码 LeetCode 53. 最大子序和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        for(int i = 0,last = 0;i < nums.size();i ++){
           last = nums[i] + max(last,0);
            res = max(res,last);
        }
        return res;
    }
};


活动打卡代码 LeetCode 52. N皇后 II

class Solution {
public:
    int n;
    vector<bool> col, dg, udg;
    vector<vector<string>> ans;
    vector<string> path;
void dfs(int u) {
        if (u == n) {
            ans.push_back(path);
            return;
        }

        for (int i = 0; i < n; i ++ ) {
            if (!col[i] && !dg[u - i + n] && !udg[u + i]) {
                col[i] = dg[u - i + n] = udg[u + i] = true;
                path[u][i] = 'Q';
                dfs(u + 1);
                path[u][i] = '.';
                col[i] = dg[u - i + n] = udg[u + i] = false;
            }
        }
    }
    int totalNQueens(int _n) {
        n = _n;
        col = vector<bool>(n);
        dg = udg = vector<bool>(n * 2);
        path = vector<string>(n, string(n, '.'));
        dfs(0);
        return ans.size();
    }
};


活动打卡代码 LeetCode 51. N 皇后

class Solution {
public:

    int n;
    vector<bool> col,dg,udg;//每一列 和两个对角线
    vector<vector<string>> ans;
    vector<string> path;
    vector<vector<string>> solveNQueens(int _n) {
        n = _n;
        col = vector<bool>(n);
        dg = udg = vector<bool>(n * 2);

        path = vector<string>(n,string(n,'.'));//初始化棋盘
        dfs(0);
        return ans;
    }
    void dfs(int u){
        if(u == n){ans.push_back(path);return;}

        for(int i = 0;i < n;i ++){
            //u = x + b 东北方向的对角线 b = u - x + n(有可能为负数 又因为是对称 所以 + n可以处理掉截距为负的可能)
            //u = -x + b 东南方向的对角线 b = u + x
            if(!col[i] && !dg[u - i + n] && !udg[u + i]){
                col[i] = dg[u - i + n] = udg[u + i] = true;
                path[u][i] = 'Q';
                dfs(u + 1);
                col[i] = dg[u - i + n] = udg[u + i] = false;
                path[u][i] = '.';
            }
        }

    }

};


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

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int a[N],g[N],f[N];
int n;
int main(){
    // while(cin >> a[i]) n ++;
    string line;
    getline(cin ,line);
    stringstream ssin(line);
    while(ssin >> a[n]) n ++;

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

    cout << res << endl;

    //用g数组存储当前所有的子序列
    int cnt = 0;//表示当前子序列的个数
    //贪心
    for(int i = 0;i < n;i ++){
        int k = 0;//序列
        //只要没有遍历完当前的序列 并且 当前的序列小于当前的数字 k ++
        while(k < cnt && g[k] < a[i]) k ++;
        //替换
        g[k] = a[i];
        if(k >= cnt)//说明没有任何一个序列大于等于当前数的
        {
            //开一个新的序列
            cnt ++;
        }
    }

    cout << cnt << endl;

    return 0;

}