Znzryb's Blog
0%

Posted on Edited on

题目大意

给定长度为 nn 的序列 AA，求其最长严格上升子序列（LIS）的长度。

AC代码

该题目实际上是要求最长上升子序列严格递增

AC https://www.luogu.com.cn/record/183531657

实际上我这题做法是O（n^2）的，不能通过下面这题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
typedef long long ll;
const ll N=5010;
// dp 里存的是以i个数为头所能组成的最长上升子序列
ll n,dp[N],A[N],ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i) {
        cin>>A[i];
    }
    for(int i=1;i<=n;++i) {
        dp[i]=1;
    }
    for(ll i=n-1;i>=1;--i) {
        for(ll j=n;j>=i+1;--j) {
            if(A[i]<A[j]) {
                dp[i]=max(dp[i],1+dp[j]);
            }
        }
    }
    for(int i=1;i<=n;i++) {
        ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;
    return 0;
}
// https://www.luogu.com.cn/record/183531657

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

给定一串导弹的高度序列（按到达顺序）。

1）求最多能用多少套“拦截系统”把所有导弹拦截完（每套系统只能拦截一个不升的序列）。

2）求这串序列的最长严格上升子序列长度。

输出两行分别为上述两个答案。

AC代码

根据题意，我们要求最长单调子序列

个人认为讲的比较好的leetcode题解，贪心

https://leetcode.com/problems/longest-increasing-subsequence/solutions/1326308/c-python-dp-binary-search-bit-segment-tree-solutions-picture-explain-o-nlogn

这种做法即维护了接纳信息，又维护了长度信息，一举两得。

然后注意写a.begin()，不要写begin（a），前面的是C++98写法

AC. https://www.luogu.com.cn/record/183637393

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// https://www.luogu.com.cn/problem/P1020
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll N=1e5+10;
ll num,A[N];
vector<ll> sub,sys;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n=0;
    while (cin>>num) {
        ++n;
        A[n]=num;
    }
    for(int i=1;i<=n;++i) {
        if(i==1)
            sub.push_back(A[1]);
        else {
            if(A[i]<=sub.back()) {
                sub.push_back(A[i]);
                continue;
            }
            ll idx=upper_bound(sub.begin(),sub.end(),A[i],greater<int>())-sub.begin();
            sub[idx]=A[i];
            //      0 1 2 3 4 5 6 7 8
            // a[]={0,8,5,4,4,3,3,1};
            // int idx3=upper_bound(begin(a)+1,end(a),3,greater<int>())-&a[0];
            // idx3==7 -> 即修改1为3，提升容纳量
        }
    }
    for(int i=1;i<=n;i++) {
         if(i==1) {
             sys.push_back(A[i]);
         }else {
             ll idx=lower_bound(sys.begin(),sys.end(),A[i])-sys.begin();
             if(idx>=sys.size())
                 sys.push_back(A[i]);
             else
                 sys[idx]=A[i];
         }
    }
    cout<<sub.size()<<endl;
    cout<<sys.size()<<endl;
    return 0;
}
// AC https://www.luogu.com.cn/record/183637393

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

给定 nn 个人，每个人有一个所属组别 teami∈{1,2,3}team_i \in \{1,2,3\} 和一个权重 sis_i。需要把所有人重新分到 3 组，使得每组权重和都等于总和的 1/31/3，并且最少改变人数（把一个人从原组分到别组算一次改变）。输出最少改变数；若无法平分则输出 −1-1。

AC代码

具体思路见此视频

【AtCoder 初学者竞赛 375比赛讲解】 【精准空降到 1:09:56】 https://www.bilibili.com/video/BV1UR26YnEpX/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=4196

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// E - 3 Team Division
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const ll N=110;
ll n,team[N],s[N],sum[4],S,object,dp[N][510][510],prefixSum[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>team[i]>>s[i];
        S+=s[i];
    }
    memset(dp,0x3f,sizeof(dp));
    register ll inf=dp[0][0][0];
    dp[0][0][0]=0;
    if(S%3!=0) {
        cout<<-1<<endl;
        return 0;
    }
    for(int i=1;i<=n;i++) {     // 就是算一个前缀和
        prefixSum[i]=prefixSum[i-1]+s[i];
    }
    object=S/3;
    for(int i=1;i<=n;++i) {
        for(int a=0;a<=object;++a) {
            for(int b=0;b<=object;++b) {
                register ll res=inf;
                if(s[i]<=a)
                    res=min(res,dp[i-1][a-s[i]][b]+(team[i] != 1));
                if(s[i]<=b)
                    res=min(res,dp[i-1][a][b-s[i]]+(team[i] != 2));
                if(s[i]<=prefixSum[i]-a-b)
                    res=min(res,dp[i-1][a][b]+(team[i] != 3));
                dp[i][a][b]=res;
            }
        }
    }
    ll ans= dp[n][object][object]==inf ? -1:dp[n][object][object];
    cout<<ans<<endl;
    return 0;
}
// AC https://atcoder.jp/contests/abc375/submissions/59007037

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

给定多组数据。每组有 nn 个物品，每个物品有两个值 AiA_i、BiB_i，需要选出恰好 kk 个物品，使得 max⁡(A)\max(A) 与所选 BB 的和构成的目标值最小（题目要求输出该最小值）。

AC代码

总体思路就是A的值只由最大Ar决定，那么其他值怎么填那？自然是使他们的B值总和最小

然后记得sumB要归0。

AC https://atcoder.jp/contests/abc376/submissions/59002823

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll N=2e5+10;
ll n,k,T,ans,B[N],sumB;
pair<ll,ll> A[N];
// struct comp {
//     bool operator()(ll a,ll b) {
//         if(B[a]!=B[b]) {
//             return B[a]<B[b];
//         }
//         return false;
//     }
// };
priority_queue<ll> pq;
bool cmp(pair<ll,ll> a,pair<ll,ll> b) {
    if(a.first!=b.first)
        return a.first<b.first;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    for(int _=1;_<=T;++_) {
        cin>>n>>k;
        priority_queue<ll> empty;
        swap(pq,empty);     // 模拟clear操作
        ans=1e18+7;sumB=0;
        for(int i=1;i<=n;++i) {
            ll ae;
            cin>>ae;
            A[i]=make_pair(ae,i);
        }
        for(int i=1;i<=n;++i) {
            cin>>B[i];
        }
        sort(&A[1],&A[n+1],cmp);
        for(int i=1;i<=k;++i) {
            sumB+=B[A[i].second];
            pq.push(B[A[i].second]);
        }
        ans=sumB*A[k].first;
        for(int i=k+1;i<=n;++i) {
            sumB-=pq.top();
            sumB+=B[A[i].second];
            pq.pop();
            pq.push(B[A[i].second]);
            ans=min(ans,sumB*A[i].first);
        }
        cout<<ans<<endl;
    }
    return 0;
}
// AC https://atcoder.jp/contests/abc376/submissions/59002823

心路历程（WA，TLE，MLE……）