【题解】力扣1626无矛盾的最佳球队

被一道力扣dp题卡了，复健之路太痛苦了

题意

$n$ 个二元组$p(i)=(a_i,b_i)$ ，求$\max \sum_{i\in A} a_i$ ，有$\forall i\in A,\forall j\in A,b_i<b_j\Rightarrow a_i>a_j$

数据范围

$n\leq 1e3,a_i\leq 1e6,b_i\leq 1e3$

分析

一开始按两个不等式来的，写了记忆化搜索，T飞了；尝试剪枝，发现两个不等号维护记忆化搜索太有问题了，看题解是DP，尝试推DP方程。

考虑取二元组$p(i)$ 时，状态可以从何转移来。

这个状态必须满足，每一个二元组要么$b_j\geq b_i$ ，要么$a_j\leq a_i$ 。

如果二元组按$a$ 大到小排序，那么考虑取$p(i)$ 时，$j\in [1,i-1]$ 的二元组$p(j)$ ，只能取$b_j\geq b_i$ ，但如果前面有和$a_i$ 相等的，不需要满足$b$ 的条件也可以取，所以我们补充一个$b$ 大到小排序，则条件只剩$b_j\geq b_i$ 一个。

那么DP方程就来了，先将二元组按$a$ 大到小排序，设$dp(i)$ 为考虑前$i$ 个二元组，取到第$i$ 个时的和最大值，有转移方程：

$dp(i)=\max\{dp(j)\}+a_i,j<i,b_j\geq b_i$

这题就这么简单秒杀了…上来就写记忆化搜索的我真是脑抽了…

代码

注：scores就是a，ages就是b

class Solution {
public:
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        int n=scores.size();
        vector<pair<int,int>> p;
        int dp[1005];
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++) 
            p.push_back({scores[i],ages[i]});
        sort(p.begin(),p.end(),greater<pair<int,int>>());
        int ans=0;
        for(int i=0;i<n;i++) {
            for(int j=0;j<i;j++)
                if(p[i].second<=p[j].second)
                    dp[i]=max(dp[i],dp[j]);
            dp[i]+=p[i].first;
            ans=max(ans,dp[i]);
        }
        return ans;
    }
};