BZOJ_1783
乍看上去大概就要dp的，细想一下确实dp是可行的，不过中文描述里面漏了句关键的话，一开始让我迷茫了一阵，后来仔细看了英文描述之后才算清楚了。
另外突发奇想用英文写了题解，大概脑子在深夜的时候总会有点诡异的想法吧……（本人六级尚未考过，如果英文太烂的话还望谅解……）
/* f[i] means the maximum weights we can get between hay bale i and hay bale N (include i and N). id[i] means which one we should choose firstly if we want to get f[i] weights between hay bale i and hay bale N (include i and N). We may choose the best choice in (1) and (2). (1) donot choose hay bale i : f[i] = f[i + 1], id[i] = id[i + 1]; (2) choose hay bale i : f[i] = w[i] + f[id[i + 1] + 1], id[i] = i. (w[i] means the weight of hay bale i) note: We should make f[N] = w[N], f[N + 1] = 0, id[N] = N initially. */ #include<stdio.h> #include<string.h> #define MAXD 700010 typedef long long LL; LL f[MAXD]; int N, id[MAXD], w[MAXD]; int main() { while(scanf("%d", &N) == 1) { for(int i = 1; i <= N; i ++) scanf("%d", &w[i]); f[N] = w[N], f[N + 1] = 0, id[N] = N; for(int i = N - 1; i >= 1; i --) { f[i] = f[i + 1], id[i] = id[i + 1]; LL t = w[i] + f[id[i + 1] + 1]; if(t >= f[i]) f[i] = t, id[i] = i; } printf("%lld %lld\n", f[1], f[id[1] + 1]); } return 0; }