7.25 mx题单（DP）题解

__S08577__ · 2024-07-25 12:02:36 · 题解

A

题意

给定一棵 n 个节点的，带有点权的树（编号从 1 开始），点权可能有负。

你需要求出这棵树的一个连通块，其点权和尽可能大。

你只需要输出那个最大的点权和，保证答案在 int 范围内。

思路

树形DP板子题。类似最大子段和。

不难推出状态转移方程：

其中，x 为当前节点，v 为 x 的儿子。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>

using namespace std;

#define ll long long

const int N=1e5+5;//注意修改
const int mod=1e9+7;

vector <int> g[N];
int a[N],f[N];

void dfs(int x,int fa){
    f[x]=a[x];
    for(int i=0;i<g[x].size();i++){
        int v=g[x][i];
        if(v==fa) continue ;
        dfs(v,x);
        f[x]=max(f[x],f[x]+f[v]);
    }
}

int main(){
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);

    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    int maxx=0;
    for(int i=1;i<=n;i++){
        maxx=max(maxx,f[i]);
    }
    cout<<maxx;
    return 0;
//    fclose(stdin);
//    fclose(stdout);
}

/*

 */

B

题意

给定一个长度为 n 的序列 A ，你可以进行任意次如下的操作：

选择两个相邻且相等的数字，把它们合并成一个数，合并结果为原数值加一。

求你能得到的最大的数字。

思路

一开始想用区间DP解，可惜数据范围 n^3 搞不了。(听说mx数据贼几把水，n^3 可过)

这道题状态十分的不好想。

设 f_{i,j} 为合并出 i ，左端点为 j，右端点的位置。

我们可以利用倍增的思想，请看下图：

又出现了一个问题：我们枚举 i 要枚举到哪个数。首先，a_i \le 40,并且 n \le 2^{18}，不难发现，i 最大就是 40+18=58 。

所以状态转移方程为：

时间复杂度：O(58n)。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>

using namespace std;

#define ll long long

const int N=5e3+5;//注意修改
const int mod=1e9+7;

vector <int> g[N];
int a[N],f[60][(1<<20)+10],b[N];

int main(){
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);

    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        f[t][i]=i+1;
    }
    int maxx=0;
    for(int i=2;i<=58;i++){
        for(int j=1;j<=n;j++){
             if(f[i][j]==0) f[i][j]=f[i-1][f[i-1][j]];
             if(f[i][j]) maxx=i;
        }
    }
    cout<<maxx;
    return 0;
//    fclose(stdin);
//    fclose(stdout);
}

/*

 */

C

题意

给定一个长度为 n 的序列 A 和一个长度为 m 的序列 B ，求它们的最长公共上升子序列。

你只需要输出该子序列的长度。

思路

板子题。

这道题是最长公共子序列和最长上升子序列的混合体。

设 f_{i,j} 为 A 序列取前 i 个数，B 序列取前 j 个数的最长公共上升子序列的长度。

当 a_i \ne b_j ，f_{i,j} = f_{i-1,j} 。

当 a_i = b_j ，f_{i,j}= \max(f_{i,j},f_{i-1,k}+1) [1\le k \le j ,b_k<b_j ]

只有 b_k<b_j 时，序列才是严格上升子序列。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>

using namespace std;

#define int long long

const int N=5e3+5;//注意修改
const int mod=1e9+7;

vector <int> g[N];
int a[N],f[N][N],b[N];

signed main(){
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);

    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int m;
    cin>>m;
    for(int i=1;i<=m;i++) cin>>b[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i]!=b[j]) f[i][j]=f[i-1][j];
            else{
                for(int k=1;k<=j;k++){
                    if(b[k]<b[j]){
                        f[i][j]=max(f[i][j],f[i-1][k]+1);
                    }
                }
            }
        }
    }
    int maxx=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            maxx=max(maxx,f[i][j]);
        }
    }
    cout<<maxx;
    return 0;
//    fclose(stdin);
//    fclose(stdout);
}

/*

 */

e

题意

给定一个长度为 n 的序列 A，下标从 1 开始。

你需要删掉一些元素，剩余元素相对位置不动，得到一个新序列 B，下标同样从 1 开始。

你的目标是最大化新序列中 B_i=i 的数量。

输出这个最大的数量。

思路

设 f_{i,j} 表示以 i 结尾，偏移量为 j 的数量。

不 难列出状态转移方程：

我们发现，当 a_i=i-j 时，这个数字刚好能对上，所以可能数要加一。

如果有偏移量，如果我们删去一个数，那么总个数减一，偏移量也减一，这里也要判断一下。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>

using namespace std;

#define int long long

const int N=5e3+5;//注意修改
const int mod=1e9+7;

vector <int> g[N];
int a[N],f[N][N],b[N];//fij表示以i结尾，偏移量为j

signed main(){
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);

    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int maxx=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<n;j++){
            int d=0;
            if(a[i]==i-j) d=1;
            f[i][j]=max(f[i][j],f[i-1][j]+d);
            if(j){
                f[i][j]=max(f[i][j],f[i-1][j-1]);
            }
            maxx=max(maxx,f[i][j]);
        }
    }
    cout<<maxx;
    return 0;
//    fclose(stdin);
//    fclose(stdout);
}

/*

 */

f

题意

给出两个长度为 n 的正整数序列 a 和 b

你需要回答 q 次询问，每次给出 [l,r]，问进行以下操作的最少次数使得 \forall i\in [l,r] \,,a_i=b_i，或报告无解

询问之间互相独立

一次操作定义为选出一个长度为 k（k 是偶数）的正整数序列 pos，满足 l\le pos_1<pos_2<\ldots<pos_{k-1}<pos_k\le r，将 a_{pos_1},a_{pos_3},\ldots,a_{pos_{k-1}} 加一，将 b_{pos_2},b_{pos_4},\ldots,b_{pos_k} 加一。

思路

不难发现，我们这个操作只与 b_i-a_i 有关，与 a_i b_i 本身无关。所以，我们设 c_i=b_i-a_i ，最终要求