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
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 */