比赛代码 - COGS

比赛	20120925	评测结果	AAAAAAAAAA
题目名称	数列游戏	最终得分	100
用户昵称	王者自由	运行时间	0.029 s
代码语言	C++	内存使用	4.67 MiB
提交时间	2012-09-25 21:14:34

显示代码纯文本

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1000 + 10, INF = 0x7ffffff;
int n, a[N], f[N][N], s;
int main() {
    freopen("seqgame.in", "r", stdin);
    freopen("seqgame.out", "w", stdout);
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        scanf("%d", a+i);
    for(int i=1; i<=n; i++) {
        f[i][0] = f[i-1][0] + (a[i] == i);
        for(int j=1; j<i; j++)
            f[i][j] = max(f[i-1][j] + (a[i] == i - j), f[i-1][j-1]);
    }
    s = *max_element(f[n]+1, f[n]+n+1);
    printf("%d\n", s);
    return 0;
}