Sweet War (AOJ1353)
A-Bにしかよらないのはまあわかる.A-Bは広い範囲の値を取るので,美味しみの方でメモりたくなる.dp[i][j]="i個目以降で(先手が)おいしみjを得るのに必要なエネルギー格差"を持って更新すればいいです.初め逆シミュレーションみたいなのをして頑張って更新をO(1)で出来ると思ったんだけどなんか合わなかったのでにぶたんした.
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; typedef long long ll; ll dp[151][152],inf=1e18; int N; ll A,B,r[150],s[150]; int lef; int geteasy(int i,ll x){ return upper_bound(dp[i],dp[i]+151,x)-dp[i]-1; } int get(int i,ll x){ int ret=0; chmax(ret,lef-geteasy(i+1,-x-r[i])); if(x>0){ chmax(ret,geteasy(i+1,x-1-r[i])); } return ret; } int main(){ int N; cin>>N>>A>>B; rep(i,N) cin>>r[i]>>s[i]; rep(i,151) rep(j,152) dp[i][j]=inf; dp[N][0]=-inf; for(int i=N-1;i>=0;i--){ lef+=s[i]; rep(j,lef+1){ ll ub=inf,lb=-inf; while(ub-lb>1){ ll m=(ub+lb)/2; if(get(i,m)>=j) ub=m; else lb=m; } dp[i][j]=ub; } } ll x=geteasy(0,A-B); cout<<x<<" "<<lef-x<<endl; }