ICPC（武汉icpc邀请赛）

题意：有n个位置排成一排，从左到右第i个座位上摆放着分量为ai的菜肴。有个人坐在第s张椅子，每秒结束，她可以移动到相邻位置上也可以不动，她坐的位置上的菜肴都会被她吃了。计算她可以吃的最大总分量。他刚开始可以选择任意位置，她的时间最多为2n。

知识点：二维dp

分析：

g[s][t] 为在位置s移动不超过t次且不折返的吃掉菜肴的最大值。对于所有情况，只有两种，一种是一直走到头不折反，一种是折返走。向左移时，对于每一个座位 s 和时间 t，由由子可以选择从左边的一个座位移动过来，即从 s-1 移动到 s。因此，f[s][t] 可以通过比较 f[s-1][t-1]（从左边移动过来时的最大份量）和 g[s][t]（不移动方向时的最大份量）来更新。向右移动，由于我们需要先处理向左移动的情况，为了避免覆盖掉还未处理的值，我们选择从右向左更新数组。对于每一个座位 s 和时间 t，由由子可以选择从右边的一个座位移动过来，即从 s+1 移动到 s。因此，我们需要先更新 g[s][t]，确保它包含了从右边移动过来时的最大份量，然后再更新 f[s][t]。

#include

using namespace std;

typedef long long ll;

const int N=5e3+10;

ll sum[N],g[N][2*N],f[N][2*N];

int a[N],n;

int main(){

    cin>>n;

    for(int i=1;i>a[i];

        sum[i]=sum[i-1]+a[i];

    }

    for(int s=1;s