M_sea

洛谷1799 数列
题目描述虽然msh长大了,但她还是很喜欢找点游戏自娱自乐。有一天,她在纸上写了一串数字:1,l,2,5,4。接着她...
扫描右侧二维码阅读全文
25
2018/07

洛谷1799 数列

题目描述

虽然msh长大了,但她还是很喜欢找点游戏自娱自乐。有一天,她在纸上写了一串数字:1,l,2,5,4。接着她擦掉了一个l,结果发现剩下1,2,4都在自己所在的位置上,即1在第1位,2在第2位,4在第4位。她希望擦掉某些数后,剩下的数列中在自己位置上的数尽量多。她发现这个游戏很好玩,于是开始乐此不疲地玩起来……不过她不能确定最多能有多少个数在自己的位置上,所以找到你,请你帮忙计算一下!

传送门

算法

很好想的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;
}
最后修改:2018 年 11 月 09 日 04 : 49 PM

发表评论

2 条评论

  1. smy

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

    1. M_sea
      @smy

      不会 qwq