Znzryb's Blog

P1725 琪露诺

Posted on 2024-10-21 Edited on 2026-02-13

题目大意

在一条直线（或编号轴）上从起点出发，每次可以从位置 $j$ 跳到 $i$ ，要求跳跃长度在区间 $[l, r]$ 内。每到达一个位置会获得或损失对应的分值。问到达“终点对岸”（位置编号超过 $n$ ）时，能得到的最大总分。

AC代码

比较裸的子序列提取dp（子序列为 [ i-r , i-l ] ），唯一需要注意的是

只要她下一步的位置编号大于N就算到达对岸。

所以你的dp范围要扩大一点

#include <iostream>
using namespace std;
typedef long long ll;
const ll N=4e5+10,inf=1e18+7;
ll n,l,r,A[N],dp[N],ans=-inf;    // dp存的是走到该点最多能够获得多少冰冻指数
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    // 移动到i+L,i+R 向前递增，无后效性
    cin>>n>>l>>r;
    for(int i=0;i<=n;i++) {
        cin>>A[i];
    }
    dp[0]=A[0];
    for(int i=1;i<=n+r;i++) {
        dp[i]=-inf;
    }
    for(int i=1;i<=n+r;i++) {
        for(int j=i-l;j>=i-r && j>=0;j--) {
            dp[i]=max(dp[j]+A[i],dp[i]);
        }
    }
    for(int i=n;i<=n+r;i++)
        ans=max(ans,dp[i]);
    cout<<ans<<endl;
    return 0;
}
// AC https://www.luogu.com.cn/record/183798861

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

P2285 [HNOI2004] 打鼹鼠

Posted on 2024-10-20 Edited on 2026-02-13

题目大意

给定若干次“鼹鼠出现”的信息：每次出现的时间 $T_i$ 与坐标 $(X_i, Y_i)$ 。初始在某个位置，每次可以在单位时间内移动一定距离（等价于曼哈顿距离不超过时间差）。问最多能打到多少只鼹鼠。

AC代码

思路见洛谷进阶篇P227

注释也算写的比较详细

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll M=1e4+10;
ll n,m,T[M],X[M],Y[M],dp[M],ans;
// dp存打了第i只鼹鼠的情况下，之前能打多少只鼹鼠(包括这第i只鼹鼠)
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        cin>>T[i]>>X[i]>>Y[i];

    }
    for(int i=1;i<=m;i++) {
        ll t=T[i],x=X[i],y=Y[i];
        dp[i]=1;
        for(int j=i-1;j>=1;j--) {
            if(t-T[j]==0) // 时间相同自然不可能状态转移
                continue;
            if(abs(x-X[j])+abs(y-Y[j])<=t-T[j]) //状态转移条件是曼哈顿距离小于时间差
                dp[i]=max(dp[i],dp[j]+1);
        }
    }
    for(int i=1;i<=m;i++) {
        ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;
    return 0;
}
// AC https://www.luogu.com.cn/record/183675211

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

B3637 最长上升子序列

Posted on 2024-10-20 Edited on 2026-02-13

题目大意

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

AC代码

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

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

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

#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……）

P1020 [NOIP1999 提高组] 导弹拦截

Posted on 2024-10-20 Edited on 2026-02-13

题目大意

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

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

// 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……）

ABC-375-E-3 Team Division

Posted on 2024-10-20 Edited on 2026-02-13

题目大意

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

AC代码

具体思路见此视频

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

// 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