思路：
▶ 设 win(i,x,y) 表示当前可以买的物品是 i，先手有 x 元，后 手有 y 元时，先手是否必胜
▶ win(i,x,y) ⇐⇒∃j((j > i)∧(x ≥ si−sj)∧¬win(j,y,x−si +sj))
▶ 其中 si = Ci + Ci+1 +···+ CN
▶ 注意到 x + y = A + B−s1 + si，即 win(i,x) := win(i,x,y)
▶ win(i,x) =⇒ win(i,x + 1)
▶ 设 m(i) = min{x : win(i,x)}，则 ¬win(i,x) ⇐⇒ x ≤ m(i)−1
▶ 令 D = A + B−s1 + si
▶ m(i) =min{x : ∃j((j > i)∧(x ≥ si −sj)∧¬win(j,D−x))}
=min{x : ∃j((j > i)∧(x ≥ si −sj)∧D−x ≤ m(j)−1}
=min{max{si −sj,D−m(j) + 1} : j > i}
=min{max{si −sj,A + B−s1 + si −m(j) + +1} : j > i}
=si + min{max{−sj,A + B−s1 −m(j) + 1} : j > i}
▶ 只要测试 A ≥ m(1)
代码如下：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define ll __int64 5 #define M 1000002 6 #define inf 1e15 7 using namespace std; 8 int c[M]; 9 ll s[M],m[M],cal,mi; 10 int main() 11 { 12 int n,q,i,a,mm,b,j; 13 while(scanf("%d%d%d",&n,&a,&b)!=EOF) 14 { 15 for(i=0;i<n;i++) scanf("%d",&c[i]); 16 s[n]=0; 17 for(i=n-1;i>=0;i--) s[i]=s[i+1]+c[i]; 18 m[n]=inf;mi=inf; 19 cal=a+b-s[0]+1; 20 for(i=n;i>=1;i--){ 21 mi=min(mi,max(-s[i],cal-m[i])); 22 m[i-1]=s[i-1]+mi; 23 } 24 puts(a>=m[0]?"ALICE":"BOB"); 25 } 26 return 0; 27 }