cqyz oj | 花园游戏

Description

　　已知：这是一个 1×N 的花园，被分成了 N 个格子，每个格子里有一种神奇的樱花，看到第 i 个格子上的花，洋娃娃会得到满足度 Ci （每个花的满足度只被计算一次）。现在洋娃娃从任意格子走进花园，当然从第 i 个格子进去会消耗 Di 个单位的满足度，然后游历花园，在一个格子向右走需要耗费 R 个单位的满足度，向左走需要耗费 L 个单位的满足度，最后从第 i 个格子出花园又要耗费 Fi 个单位的满足度。

　　接下来，需要设计一套游历方案，使得最终获得的总满足度最高。

Input

　　第一行依次给出三个正整数N，L，R。　　第二行有N个整数，第i个数为Di。　　第三行有N个整数，第i个数为Fi。　　第四行有N个整数，第i个数为Ci。

Output

　　仅需要输出一行包括一个整数，表示最大获得的满足度为多少。

Sample Input 1

5 1 1
1 1 1 1 1
1 1 1 1 1
1 1 3 1 1

Sample Output 1

Hint

对于30%数据，N<=10。

对于60%数据，N<=100。

对于100%数据，N<=1000，0<=L,R,D[i],F[i],C[i]<=1000000。

错误的贪心：枚举i,j，找从i进直接走到j出去的最大值。

错误原因：每个格子价值只计算一次，但是可以反复走，即可以先把一边的格子走过再回头从另一边出去。

所以要考虑从i进，先去完一边的格子，回头取完另一边的格子再走到j出去。

计算时可以先预处理，算出从i向左走和向右走再回到i能得到的最大值。

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define inf 1000000010
using namespace std;

const int maxn = 1005;
int max(int a,int b){return a>b?a:b;}
int n, lc, rc;
int D[maxn], F[maxn], C[maxn];
int l[maxn], r[maxn], q[maxn];

void data_in(){
    scanf("%d%d%d", &n, &lc, &rc);
    for(int i=1;i<=n;i++) scanf("%d", &D[i]);
    for(int i=1;i<=n;i++) scanf("%d", &F[i]);
    for(int i=1;i<=n;i++) scanf("%d", &C[i]), q[i] = q[i-1] + C[i];
}

void pre(){
    for(int i=1;i<=n;i++) l[i] = r[i] = -inf;
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++)
            l[i] = max(l[i], q[i-1] - q[j-1] - (lc+rc)*(i-j));
        l[i] = max(l[i], 0);
    }
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++)
            r[i] = max(r[i], q[j] - q[i] - (lc+rc)*(j-i));
        r[i] = max(r[i], 0);
    }
}

void solve(){
    int ans = -inf;
    //i in j out
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        if(i>j) ans = max(ans, q[i] - q[j-1] + r[i] + l[j] - D[i] - F[j] - lc*(i-j));
        else if(i == j) ans = max(ans, C[i] + l[i] + r[i] - D[i] - F[i]);
        else ans = max(ans, q[j] - q[i-1] + l[i] + r[j] - D[i] - F[j] - rc*(j-i));
    printf("%d", ans);
}

int main(){
    
    data_in();
    pre();
    solve();
    
    return 0;
}
/*
5 1 1
1 1 1 1 1
1 1 1 1 1
1 1 3 1 1

*/

View Code