82分求助

第3个和第10个测试点第二问全部输出0 求助

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 515, INF = 1e7;
struct Edge{
    int ss, e, nex, w, flow;
}edge[4 * maxn * maxn];
int xl[maxn], n, f[maxn], s, t, head[maxn], tot, ans, dep[maxn], q[maxn * 10]; 
inline int id(int a, int id){
    return 2 * a + id;
}
inline void add(int ss, int ee, int w){
    edge[++tot] = {ss, ee, head[ss], w, 0};
    head[ss] = tot;
    edge[++tot] = {ee, ss, head[ee], 0, 0};
    head[ee] = tot;
}
inline bool find(){
    memset(dep, 0, sizeof(dep));
    int l, r, cur;
    l = r = 1;
    q[1] = s;
    dep[s] = 1;
    while(l <= r){
        cur = q[l++];
        for(int i = head[cur], e; i; i = edge[i].nex){
            e = edge[i].e;
            if(edge[i].w > edge[i].flow && !dep[e]){
                q[++r] = e;
                dep[e] = dep[cur] + 1;
                if(e == t)  return true;
            }
        }
    }
    return false;
}
int dfs(int cur, int now){
    if(cur == t || now <= 0)    return now;
    int t = now, delta;
    for(int i = head[cur], e; i; i = edge[i].nex){
        e = edge[i].e;
        if(edge[i].w > edge[i].flow && dep[e] == dep[cur] + 1){
            delta = dfs(e, min(t, edge[i].w - edge[i].flow));
            if(delta <= 0)  dep[e] = 0;
            edge[i].flow += delta;
            edge[((i - 1) ^ 1) + 1].flow -= delta;
            t -= delta;
            if(t == 0)  break;
        }
    }
    return now - t;
}
inline void dinic(){
    ans = 0;
    while(find()){
        ans += dfs(s, INF);
    }
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &xl[i]);
    int ans1 = 1;
    for(int i = n; i >= 1; i--){
        f[i] = 1;
        for(int j = n; j > i; j--)
            if(xl[j] >= xl[i])
                f[i] = max(f[i], f[j] + 1);
        ans1 = max(ans1, f[i]);
    }
    printf("%d\n", ans1);
    s = 1; t = 2 * n + 2;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j < i; j++)
            if(xl[j] <= xl[i] && f[j] - 1 == f[i])
                add(id(j, 1), id(i, 0), 1);
    for(int i = 1; i <= n; i++){
        add(id(i, 0), id(i, 1), 1);
        if(f[i] == ans1)    add(s, id(i, 0), 1);
        if(f[i] == 1)   add(id(i, 1), t, 1);
    }
    dinic();
    printf("%d\n", ans);
    for(int i = 1; i <= tot; i++){
        edge[i].flow = 0;
        if(edge[i].ss == 1 && edge[i].e == 2)   edge[i].w = INF;
        if(edge[i].ss == 2 && edge[i].e == 3)   edge[i].w = INF;
        if(edge[i].ss == 2 * n && edge[i].e == 2 * n + 1)   edge[i].w = INF;
        if(edge[i].ss == 2 * n + 1 && edge[i].e == 2 * n + 2)   edge[i].w = INF;
    }
    dinic();
    printf("%d\n", ans);
    return 0;
}