【学习笔记】CF704B Ant Man

感觉智商还是不太够

智商不够啊，咋想到贪心的😅

非常经典的贪心模型🤔

首先，从小到大将每个$i$插入到排列中，用$DP$记录还有多少个位置可以插入，可以通过钦定新插入的位置左右两边是否继续插入数来提前计算贡献。注意分$i$和$s,t$的大小关系讨论。这个做法的时间复杂度是$O(n^2)$，并且转移的情况比较多，估计要调半天。

但是注意到，我们可以 直接贪心 。发现本质上就是每次加入两个固定的数，然后将原来的一个数替换掉，并且一个数只能被替换一次。因此每次贪心的选最优的位置插入即可。

代码可以在$5\min$内完成。

另一道直接贪心的题：CF573E Bear and Bowling

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=5005;
int n,s,t,to[N];
ll a[N],b[N],c[N],d[N],X[N],res;
ll calc(int i,int j){
    if(i>j)return X[i]-X[j]+c[i]+b[j];
    return X[j]-X[i]+d[i]+a[j];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>s>>t;
    for(int i=1;i<=n;i++)cin>>X[i];
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=1;i<=n;i++)cin>>d[i];
    to[s]=t;
    for(int i=1;i<=n;i++){
        if(i==s||i==t)continue;
        pair<ll,int>tmp={inf,0};
        for(int j=s;j!=t;j=to[j]){
            tmp=min(tmp,{calc(j,i)+calc(i,to[j])-calc(j,to[j]),j});
        }to[i]=to[tmp.se],to[tmp.se]=i;
    }for(int i=s;i!=t;i=to[i])res+=calc(i,to[i]);
    cout<<res;
}