头像

Elpsy_3




离线:4小时前


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

Elpsy_3
10小时前
#include <sstream>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int h[N], f[N], q[N];

int main()
{
    string line;
    getline(cin, line);
    stringstream ssin(line);
    while (ssin >> h[n]) n ++ ;

    int res = 0, cnt = 0;//cnt为导弹系统数
    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);
        res = max(res, f[i]);

        int k = 0;//表示当前遍历到了第几个导弹系统
        //q[K]表示第k套导弹系统所拦截的最后一个导弹的高度
        while (k < cnt && q[k] < h[i]) k ++ ;//如果第k个导弹比当前数小,说明无法插入,k++
        if (k == cnt) q[cnt ++ ] = h[i];
        else q[k] = h[i];
    }

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



Elpsy_3
1天前
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int dp[N],n,a[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        dp[i]=a[i];
        for(int j=1;j<=n;j++)
        {
            if(a[j]<a[i])
            {
                dp[i]=max(dp[i],dp[j]+a[i]);
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,dp[i]);
    printf("%d",res);
    return 0;
}


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

Elpsy_3
1天前
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int dp[N],n,a[N],dpp[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        dp[i]=1;
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i])
            {
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    for(int i=n;i>=1;i--)
    {
        dpp[i]=1;
        for(int j=n;j>i;j--)
        {
            if(a[j]<a[i])
            {
                dpp[i]=max(dpp[i],dpp[j]+1);
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,dp[i]+dpp[i]-1);
    printf("%d",n-res);
    return 0;
}


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

Elpsy_3
1天前
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=5010;
int dp[N],n;
PII q[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&q[i].first,&q[i].second);
    sort(q+1,q+n+1);
    for(int i=1;i<=n;i++)
    {
        dp[i]=1;
        for(int j=1;j<i;j++)
        {
            if(q[j].second<q[i].second)
            {
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,dp[i]);
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 1014. 登山

Elpsy_3
1天前
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int dp[N],a[N],dpp[N],n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        dp[i]=1;
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i])
            {
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    for(int i=n;i>=1;i--)
    {
        dpp[i]=1;
        for(int j=n;j>i;j--)
        {
            if(a[j]<a[i])
            {
                dpp[i]=max(dpp[i],dpp[j]+1);
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,dp[i]+dpp[i]-1);
    cout<<res;
    return 0;
}



Elpsy_3
1天前
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=110;
int k,n;
int dp[N];
int a[N];
int main()
{
    cin>>k;
    while(k--)
    {
        int res=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        //求向左跳
        for(int i=1;i<=n;i++)//从前往后枚举,即从左往右求最长上升子序列,最右边是最大值
        {
            dp[i]=1;
            for(int j=1;j<i;j++)
            {
                if(a[j]<a[i])
                {
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
            res=max(res,dp[i]);
        }
        memset(dp,sizeof dp,0);
        //求向右跳
        for(int i=n;i>=1;i--)//从后往前枚举,即从右往左求最长上升子序列,最左边是最大值
        {
            dp[i]=1;
            for(int j=n;j>i;j--)
            {
                if(a[j]<a[i])
                {
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
            res=max(dp[i],res);
        }
        cout<<res<<endl;
    }
    return 0;
}



Elpsy_3
4天前

双指针算法

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int>heap;
        int res=0;
        for(int i=0,j=0;i<s.size();i++)
        {
            heap[s[i]]++;
            while(heap[s[i]]>1) heap[s[j++]]--;
            res=max(res,i-j+1);
        }
        return res;
    }
};


活动打卡代码 AcWing 2. 两数相加

Elpsy_3
4天前
虚拟头结点dummy,只要l1或者l2不为空或者t不为0即存在进位,即继续
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        auto dummy=new ListNode(-1),cur=dummy;
        int t=0;
        while(l1 || l2 || t)
        {
            if(l1) t+=l1->val,l1=l1->next;
            if(l2) t+=l2->val,l2=l2->next;
            cur->next=new ListNode(t%10);//在第一次时使得dummy->next变为了存储个位数的那个结点
            cur=cur->next;
            t/=10;
        }
        return dummy->next;
    }
};


活动打卡代码 LeetCode 1. 两数之和

Elpsy_3
4天前
哈希表实现插入查询
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int>heap;
        for(int i=0;i<nums.size();i++)
        {
            int r=target-nums[i];
            if(heap.count(r)) return{heap[r],i};
            heap[nums[i]]=i;
        }
        return {};
    }
};


活动打卡代码 AcWing 275. 传纸条

Elpsy_3
4天前
#include<iostream>
#include<algorithm>
using namespace std;
const int N=55;
int dp[N*2][N][N];
int g[N][N];
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&g[i][j]);
        }
    }
    for(int k=2;k<=n+m;k++)
    {
        for(int i1=1;i1<=n;i1++)
        {
            for(int i2=1;i2<=n;i2++)
            {
                if(k-i1>=1&&k-i1<=m&&k-i2>=1&&k-i2<=m)
                {
                    if(i1!=i2||k==2||k==n+m)//两者走的点不一样或者是起点和终点才可更新
                    {
                        int t=g[i1][k-i1]+g[i2][k-i2];
                        dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1-1][i2-1]+t);
                        dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1-1][i2]+t);
                        dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1][i2]+t);
                        dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1][i2-1]+t);
                    }
                }
            }
        }
    }
    cout<<dp[n+m][n][n];
    return 0;
}