比赛的时候没注意数据范围...最后一分钟没有找出bug。
结果最后的结果是int爆了
惨痛的教训!

题目大意:
在两个长度为n的队伍中选若干个人,使身高总和最大。不能连续从一个队伍中选人,但可以跳过。

#include <bits/stdc++.h>
#define MAXN 100001
using namespace std;

int n;
long long a[MAXN];
long long b[MAXN];
long long dp[MAXN][3];

int main() {
    ios::sync_with_stdio(false);

    cin >> n;

    for ( int i = 1; i <= n; ++i )
        cin >> a[i];

    for ( int i = 1; i <= n; ++i )
        cin >> b[i];

    dp[1][0] = a[1];
    dp[1][1] = b[1];
    for ( int i = 1; i <= n; ++i ) {
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a[i];
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + b[i];
        dp[i][2] = max(dp[i-1][0], dp[i-1][1]);
    }

    cout << max(dp[n][1], max(dp[n][0], dp[n][2])) << endl;

    return 0;
}
Last modification:July 18th, 2019 at 01:58 am
博客维护不易,如果你觉得我的文章有用,请随意赞赏