2 条题解

  • 0
    @ 2026-1-28 14:22:06

    看着感觉无法贪心,观察发现数据范围较小,可以n方DP。 每个位置要么逆序要么不逆序,DP前缀以这个位置结尾的最小代价,分是否逆序,状态转移直接暴力枚举上一个是啥。

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    
    const int INF = 0x3f3f3f3f3f3f3f3f;
    
    void sol(){
        int n, c1, c2; cin >> n >> c1 >>c2;
        vector<int> a(n + 5), b(n + 5);
        vector<int> dp(n + 5, INF), dpf(n + 5, INF);
        for(int i = 1; i <= n; i ++)    cin >> a[i] >> b[i];
        a[0] = b[0] = 0;
        dp[0] = dpf[0] = 0;
        for(int i = 1; i <= n; i ++){
            for(int j = 0; j < i; j ++){
                if(a[i] >= a[j] && b[i] >= b[j]){
                    dp[i] = min(dp[i], (i - j - 1) * c1 + dp[j]);
                    dpf[i] = min(dpf[i], (i - j - 1) * c1 + dpf[j] + c2);
                }
                if(a[i] >= b[j] && b[i] >= a[j]){
                    dp[i] = min(dp[i], (i - j - 1) * c1 + dpf[j]);
                    dpf[i] = min(dpf[i], (i - j - 1) * c1 + dp[j] +c2);
                }
            }
        }
        int res = INF;
        for(int i = 0; i <= n; i ++){
            int t = min(dp[i], dpf[i]);
            res = min(res, (n - i) * c1 + t);
        }
        cout << res << endl;
    }
    
    signed main(){
        int t; cin >> t;
        while(t --)
            sol();
    }
    

    信息

    ID
    161
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    20
    已通过
    5
    上传者