题解 P1799 【数列_NOI导刊2010提高(06)】

· · 题解

没有C++的一维数组dp吗?(逃。。。

本题思路:

  1. 首先考虑状态:前\ i个数中剩下\ j个数时的最佳匹配数(无后效性的原因引用一下:第i个数最终所在的位置,只与i之前所去掉的数有关,而且只和去掉的个数有关,与具体去掉哪些数无关。)
  2. 状态转移方程:如果这个数与剩下的数相同,f[j]=max(f[i-1][j],f[i-1][j-1]);否则\ f[j]=max(f[i-1][j],f[i-1][j-1]+1)。
  3. 将数组第一维优化滚动即可。

代码如下:

PS:有些英文注释懒得删了,大佬勿喷

#include<cstdio>
using namespace std;

int n,a,ans;
int f[1001];
//  f[1001][1001] -> the first dimension is optimized
//Before i numbers, there are j numbers left

inline int max(const int &a,const int &b){return(a>b?a:b);}
int main()
{
    scanf("%d",&n);
    for(register int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        for(register int j=i;j>=1;j--)
            f[j]=max(f[j],f[j-1]+(a==j?1:0));
            //f[j]=max(f[i-1][j],f[i-1][j-1]+(a==j?1:0));
    }
    for(register int i=0;i<=n;i++)  ans=max(ans,f[i]);//f[n][i]
    printf("%d",ans);
    return 0;
}