4600: 【GESP2312六级】闯关游戏

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

输入

第一行两个整数$N$,$M$ ，分别表示关卡数量和每关的通道数量。
接下来一行$M$ 个用单个空格隔开的整数$a_0,a_1,...a_{M-1}$ 。保证$1\le a_i\le N$ 。
接下来一行$N$ 个用单个空格隔开的整数$b_0,b_1,...,b_{N-1}$ 。保证$|b_i|\le 10^5$ 。

输出

一行一个整数，表示你通关时最多能够获得的分数。

样例输入 复制 

6 2
2 3
1 0 30 100 30 30

样例输出 复制 

131

提示

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <iostream>
#include <cmath>
using namespace std;
const int N = 10005;
const int M = 105;
const int inf = 0x3f3f3f3f;
int a[M], b[N], f[N];
int main() {
    // freopen("data/1.in", "r", stdin);
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i ++)
        scanf("%d", &a[i]);
    for (int i = 0; i < n; i ++)
        scanf("%d", &b[i]);
    
    memset(f, -0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i < n; i ++)
        for (int j = 1; j <= m; j ++)
            if (i - a[j] >= 0)
                f[i] = max(f[i], f[i - a[j]] + b[i - a[j]]);
    
    int ans = -inf;
    for (int i = 0; i < n; i ++)
        for (int j = 1; j <= m; j ++)
            if (i + a[j] >= n) {
                ans = max(ans, f[i] + b[i]);
                break ;
            }
    
    cout << ans << endl;
    return 0;
}

来源/分类

提交提交记录统计露一手!