Skip to content

14020: 【原4020】数列游戏

题目

题目描述

author: Naïve Yan 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4020 

Description

在纸上写了一串数字:1,1,2,5,4。接着,擦掉了一个1,结果发现剩下1,2,4都在自己所在的位置上,即1在第1位,2在第2位,4在第4位。现在,我们希望擦掉某些数后,剩下的数列中在自己的位置上的数尽量多。

Input Format

第一行为一个数n(n ≤ 1000),表示数列的长度。

接下来一行为n个用1个空格隔开的正整数,第i行表示数Ai。

Output Format

输出一行一个整数,表示擦掉某些数后,最后剩下的数列中最多能有多少个数在自己的位置上,即Ai=i最多能有多少。

Sample Input

5 1 1 2 5 4 
20 4 6 12 14 10 20 11 9 16 5 13 2 7 18 19 1 3 17 8 15

Sample Output

3
3

zqy2018's solution

#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int n,a[1005],f[1005][1005]={0};
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}    
void init(){
    n=read();
    for(int i=1;i<=n;i++)a[i]=read(); 
}
void solve(){
    for(int i=1;i<=n;i++){
        int maxi=0;
        for(int j=i;j<=n;j++)
            maxi=max(maxi,f[i-1][j-1]),
            f[i][j]=maxi+(a[j]==i);
    }
    int ans=0;
    for(int i=1;i<=n;i++)ans=max(ans,f[i][n]);
    printf("%d\n",ans);
}
int main(){
    init();
    solve();
    return 0;
}