Cod sursa(job #1251953)

Utilizator dinuandAndrei-Mario Dinu dinuand Data 30 octombrie 2014 08:33:05
Problema Oo Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>
#include <string.h>

#define MAXN 100001
#define INF 0x3f3f3f3f

int maxim(int a, int b)
{
    return (a > b) ? a : b;
}

int compute_dp(int start, int stop, int *dp, int *v)
{
    int i, tmp;
    for (i = start; i <= stop; i++) {
        dp[i] = maxim(v[i - 1] + v[i] + dp[i - 3], dp[i - 1]);
    }
    tmp = dp[stop];
    memset(dp, 0, sizeof(dp));
    return tmp;
}

int main()
{
    FILE *fdin = fopen("oo.in", "r");
    FILE *fdout = fopen("oo.out", "w");
    int v[MAXN], dp[MAXN], n, i, ret, sol;
    fscanf(fdin, "%d", &n);
    for (i = 1; i <= n; i++)
        fscanf(fdin, "%d", &v[i]);
    // case1: taking (1, 2)
    dp[2] = dp[3] = dp[4] = v[1] + v[2];
    sol = dp[2];
    ret = compute_dp(5, n - 1, dp, v);
    if (ret > sol) sol = ret;
    // case2: taking (1, n)
    dp[1] = dp[2] = dp[3] = v[1] + v[n];
    ret = compute_dp(4, n - 2, dp, v);
    if (ret > sol) sol = ret;
    // case3: the rest of it
    dp[0] = dp[1] = dp[2] = 0;
    ret = compute_dp(3, n, dp, v);
    if (ret > sol) sol = ret;
    fprintf(fdout, "%d\n", sol);
    fclose(stdin);
    fclose(stdout);
    return 0;
}