题解 P1799 【数列_NOI导刊2010提高(06)】
没有C++的一维数组dp吗?(逃。。。
本题思路:
- 首先考虑状态:前
\ i 个数中剩下\ j 个数时的最佳匹配数(无后效性的原因引用一下:第i个数最终所在的位置,只与i之前所去掉的数有关,而且只和去掉的个数有关,与具体去掉哪些数无关。) - 状态转移方程:如果这个数与剩下的数相同,
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) 。 - 将数组第一维优化滚动即可。
代码如下:
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;
}