记录编号	38458	评测结果	AAAAAAAAAA
题目名称	[SOJ 1137] 河床	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.061 s
提交时间	2012-04-19 13:32:01	内存使用	0.38 MiB

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 30000 + 10, K = 100 + 10;
int n, k, t, s = 1, d[N], f[2][K], o;
int main() {
    freopen("riverbed.in", "r", stdin);
    freopen("riverbed.out", "w", stdout);
    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; i++)
        scanf("%d", d+i);
    for(int i=0; i<=k; i++) f[o][i] = 1;
    for(int i=2; i<=n; i++) {
        for(int j=0; j<=k; j++) {
            t = d[i-1] - d[i] + j;
            if(t >= 0 && t <= k)
                f[o][j] = f[!o][t] + 1;
            else f[o][j] = 1;
            s = max(s, f[o][j]);
        }
        o = !o;
    }
    printf("%d\n", s);
    return 0;
}