错题本

动态规划

P1493 分梨子 - 洛谷 | 计算机科学教育新生态 - 类似动态规划的思想，难点在于对遍历顺序的确定 - 等式转化为 \(C_{1}A_{i}+C_{2}B_{i}-C_{3}\leq C_{1}A_{0}+C_{2}B_{0}\) 即左侧为关于 \(i\) 的函数 - 可以直接求出对于所有的 \(i\) 左侧的值的序列 \(d\)，接下来枚举 \(A_{0}B_{0}\) 寻找最大值（\(O(n^3)\)） - 对 d 进行排序，\(AB\) 对 \(B\) 排序，外层枚举 \(A\) 内层枚举 \(B\) 这样就是一个递增的过程，d 被逐渐加入结果。并且由于 B 已经排序，并且有条件 \(A_{i}\geq A_{0}\&\&B_{i}\geq B_{0}\) 因此 B 每次失效的恰好是上一个值的数目，维护并删除即可，这样时间复杂度就变成了 \(O(n^2)\)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int n;
    cin>>n;
    int c1,c2,c3;
    cin>>c1>>c2>>c3;
    vector<pair<int,int>>arr(n);
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        arr[i]={a,b};
    }
    vector<vector<int>>d(n,vector<int>(3)); 
    for(int i=0;i<n;i++){
        d[i][0]=c1*arr[i].first+c2*arr[i].second-c3;
        d[i][1]=arr[i].first;
        d[i][2]=arr[i].second;
    }
    sort(d.begin(),d.end());
    sort(arr.begin(),arr.end(),[&](pair<int,int>&a,pair<int,int>&b){
        return a.second<b.second;
    });
    int res=0;
    for(int i=0;i<n;i++){
        int temp=0;
        int mp[2005];
        memset(mp,0,sizeof(mp));
        for(int j=0,k=0;j<n;j++){
            int sum=c1*arr[i].first+c2*arr[j].second;
            while(k<n && d[k][0]<=sum){
                if(d[k][1]>=arr[i].first&&d[k][2]>=arr[j].second){
                    temp++;
                    mp[d[k][2]]++;
                }
                ++k;
            }
            if(j>0){
                temp-=mp[arr[j-1].second];
                mp[arr[j-1].second]=0;
            }
            res=max(res,temp);
        }
    }
    cout<<res<<endl;
    return 0;
}