M_sea

洛谷1799 数列
Luogu算法很好想的DP。设$f[i][j]$表示前i个数留下j个数的最大匹配数。当$a[i]=j$时,可以把这...
扫描右侧二维码阅读全文
25
2018/07

洛谷1799 数列

Luogu

算法

很好想的DP。

设$f[i][j]$表示前i个数留下j个数的最大匹配数。

当$a[i]=j$时,可以把这个数删掉,即为$f[i-1][j]$,也可以把这个数留下,即为$f[i-1][j-1]+1$。合起来得到:$f[i][j]=max(f[i-1][j],f[i-1][j-1]+1)$。

当$a[i]\neq j$时,同理,$f[i][j]=max(f[i-1][j],f[i-1][j-1])$。

最后答案为$max(f[n][k])\ (1\leq k \leq n)$。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

inline int MAX(int a,int b) { if (a>b) return a; else return b; }

const int MAXN=1000+10;

int f[MAXN][MAXN]; //f[i][j]表示前i个数留下j个的最大匹配数
int a[MAXN];

int main() {
    int n=read();
    for (re int i=1;i<=n;i++) a[i]=read();
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=i;j++) {
            if (a[i]==j) f[i][j]=MAX(f[i-1][j],f[i-1][j-1]+1);
            else f[i][j]=MAX(f[i-1][j],f[i-1][j-1]);
        }
    int ans=-1;
    for (re int i=1;i<=n;i++) ans=MAX(ans,f[n][i]);
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 05 月 26 日 02 : 34 PM

2 条评论

  1. smy

    一维(不是您这个状态压维)状态了解一下

    1. M_sea
      @smy

      不会 qwq

发表评论