求hack/证明复杂度/证明正确性

题面

#include<bits/stdc++.h>
#define N 5009
using namespace std;
void file() {
    freopen("robber.in","r",stdin);
    freopen("robber.out","w",stdout);
}
inline int read() {
    int x=0,y=0;
    char c=getchar();
    while(!isdigit(c)) y|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return y?-x:x;
}
inline void write(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar('0'+x%10);
}
struct robber {
    int a,b,c;
} rb[N];
bool cmp(const robber&x,const robber&y) {
    return x.c>y.c;
}
int n,matched[N];
bool match(int i,int l,int r) { //判断i号强盗能否在[l,r]之间被匹配
    if(l>r) return 0;//无效情况
    int j=matched[l];//j为原先匹配l的强盗
    if(!j) { //原先就没人匹配，那i号直接匹配上
        matched[l]=i;
        return 1;
    }
    if(rb[i].b<rb[j].b) { //有让位的希望
        if(match(j,l+1,rb[j].b)) { //可以让位
            matched[l]=i;//那就让i在l，j去后面
            return 1;
        } else return 0;
    } else {
        return match(i,l+1,r);//原先的强盗无法让位，那只能往后看看了
    }
}
int main() {
    file();
    n=read();
    for(int i=1; i<=n; ++i) rb[i].a=read(),rb[i].b=read()-1,rb[i].c=read();
    sort(rb+1,rb+1+n,cmp);//按照强盗的价值降序排列
    int ans=0;
    for(int i=1; i<=n; ++i)
        if(match(i,rb[i].a,rb[i].b))//如果i号强盗可以匹配，那ans就加上他的价值
            ans+=rb[i].c;
    write(ans),putchar('\n');
    return 0;
}