题解

1 条题解

  • 0
    @ 2017-09-09 15:05:18

    //-------------------------------------------AC code-------------------------------------------//

    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    
    using namespace std;
    
    const int MAXN = 30005;
    const int MAXM = 100005;
    int n, m, d, a, mon[MAXN];
    int dp[MAXN][1001], ans;
    
    inline int f(int x){
        return x - d + 255;
    }
    
    int main(){
    //  freopen("pick.in", "r", stdin);
    //  freopen("pick.out", "w", stdout);
        scanf("%d%d%d", &n, &m, &d);
        for(int i = 1; i <= m; i++)
            scanf("%d", &a), mon[a]++;
        memset(dp, 0xcf, sizeof dp);
        dp[d][f(d)] = mon[d];
        ans = mon[d]; 
        for(int i = d+1; i <= n; i++){
            for(int j = max(1, d-250); j <= min(i, d+250); j++){
                dp[i][f(j)] = max(dp[i-j][f(j-1)], max(dp[i-j][f(j)], dp[i-j][f(j+1)])) + mon[i];
                ans = max(ans, dp[i][f(j)]);
            }
        }
        printf("%d", ans);
        return 0;
    }
    
  • 1

信息

难度
8
分类
(无)
标签
递交数
29
已通过
3
通过率
10%
上传者