题解 - 南师大算法竞赛域

19210237 (笨笨童年) LV 8 @ 1 年前

//
//  main.cpp
//  2
//
//  Created by 汪汪队 on 2023/7/8.
//

#include<iostream>
#include<algorithm>
#include<set>
#include<unordered_map>
#include<queue>
#include<vector>
#define int long long
using namespace std;

const int N=200010;

int dp[N];

int min(int a,int b,int c){
    return min(min(a,b),c);
}

void test(){
    int n;
    cin>>n;
    vector<int>p(n+2);
    for (int i=0; i<n; i++) {
        cin>>p[i];
        dp[i]=0x3f3f3f3f;
    }
    unordered_map<int,int>_map;
    dp[0]=1;
    _map[p[0]]=0;
    for (int i=1; i<n; i++) {
        int k=p[i];
        
        if(!_map.count(k)){
            _map[k]=i;
            dp[i]=min(dp[i],dp[i-1]+1);
        }
        
        else{
            
            dp[i]=min(dp[_map[k]-1],dp[i-1]+1,dp[i]);
//            _map[k].push_back(i);
            
            if(dp[i-1]<dp[_map[k]-1]) _map[k]=i;
            
//            for (int j=0; j<_map[k].size(); j++) {
//                if(_map[k][j]==0){
//                    dp[i]=0;
//                    break;
//                }
//                dp[i]=min(dp[_map[k][j]-1],dp[i-1]+1,dp[i]);
//            }
            
        }
        
    }
    
//    for (int i=0; i<n; i++) {
//        cout<<dp[i]<<" ";
//    }
//    cout<<endl;

    cout<<n-dp[n-1]<<endl;
    return;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n; cin>>n;
    while (n--) {
        test();
    }
    
    return 0;
}

0
周旻硕 (njnu19210436) LV 10 MOD @ 1 年前
F. Tenzing and Balls

Solution

Analysis

我们用数值来代表每个小球的颜色，题意即为每次操作可以取出序列中两个数值相同的之间的所有数（包括这两个数），并且将序列变成删除子序列后的新序列。

分析题目，显然：
- 对于 $a < b < c < d$ 显然我们不可能删除同时范围 $(a, c)$ 和 $(b, d)$ ，因为当我们删除序列 $[a, c]$ 后序列将会变成 $[c, d]$ 。
- 如果我们同时删除范围 $(a, d)$ 和 $(b, c)$ ，最终得到的新序列应该与仅删除范围 $(a, d)$ 结果相同，换句话说：当序列 $[b, c] \subset [a, d]$ 时，结果即为删除序列 $[a, d]$ ，我们只需要进行一次操作即可。
那么，经过上述分析，我们可以假设：

在我们所寻求的最优解中，所有删除的子序列都是不相交的。

因此，问题等价为：我们需要找到一些不相交的子序列集合 $A_n = \{ a[l_i, r_i], i\in [1, n] \}$ ，

使得对于 $\forall \ a[l_i, r_i] \bigcap a[l_j, r_j] = \varnothing (i,j \in [1,n])$ 并且 $a[l_i] = a[r_i]$ ，同时我们也需要最大化 $\sum_{i=1}^n (r_i - l_i + 1)$ 的值。

Conclusion

考虑使用动态规划解决等价问题，令 $dp_i$ 代表在子序列前端 $a[1 \cdots n]$ 中==不删除的点==的最小数量，那么最终我们需要的最大值就是总数量减去前 $n$ 个数中不删除的点的最小数量。

分析状态转移，用 $j$ 来代表我们状态转移中寻求的索引， $dp_j$ 即代表为每个数值 $x$ 存储的满足 $a[j+1]=x$ 的最小值，分析能否寻找到这样的索引 $j$ ，我们可以得到：
- 如果我们无法寻找到一个索引 $j$ 使得 $a[j+1] = a[i]$ ，即我们无法删除子序列 $a[j+1 \cdots i]$ ，此时状态转移为 $dp_i = dp_{i-1} + 1$ 。
- 若果我们可以寻找到一个索引 $j$ 使得 $a[j+1] = a[i]$ ，即我们能够删除子序列 $a[j+1 \cdots i]$ ，此时状态转移为在 $a[j+1]=a[i]$ 且 $j + 1 < i$ 的情况下求解 $dp_i = min\{dp_j\}$ 。
综合所有情况，我们得出最终的状态转移方程：
\[
dp_i = min(dp_{i - 1} + 1, \ min\{dp_j | j+1<i, a[j+1]=a[i]\})
\]
我们预先为每个数值 $x$ 存储满足 $a[j + 1] = x$ 的最小 $dp_j$ ，这样计算每个 $dp$ 的时间复杂度为 $\Theta(n)$ 。

Code
#include <bits/stdc++.h> #define mod 998244353 #define N 200005 #define INI 1000000000 using namespace std; using ll = long long int; int n, a[N], dp[N], mn[N]; void solve() { cin >> n; dp[0] = 0; dp[1] = 0; for(int i = 1; i <= n; i++) { mn[i] = INI; } for(int i = 1; i <= n; i++) { cin >> a[i]; dp[i] = min(dp[i - 1] + 1, mn[a[i]]); mn[a[i]] = min(mn[a[i]], dp[i - 1]); } cout << n - dp[n] << endl; } int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int T = 1; cin >> T; while (T--) solve(); return 0; }
Copy

ID: 1430
难度: (无)
分类: (无)
标签: (无)
递交数: 0
已通过: 0
通过率: ?
上传者: njnu19210225 (季润民)

题解

2 条题解

F. Tenzing and Balls

Solution

Analysis

Conclusion

Code

2-6 Tenzing and Balls

信息

状态

开发

支持

题解

2 条题解

F. Tenzing and Balls

Solution

Analysis

Conclusion

Code

2-6 Tenzing and Balls

信息

状态

开发

支持

还没有账户？

登录