D - Wandering
・問題URL
https://atcoder.jp/contests/abc182/tasks/abc182_d
・発想
・ぜんぶでN²/2回くらい動くのでシミュレーションは無理。
・最初見たとき「累積和の累積和」的なものをN種類求めてうまくいくのでは?と考えたが間違い。なぜなら各動作の終わりで最大になるとは限らないから。
・解法
各動作を独立として考えたとき、移動前と後の相対座標の最大値をそれぞれ別で求めておく。今の座標+その最大値が答えか?それとも一回動作をすべてやった時の座標+次の最大値が答えか?を一重ループで求める。
・コード
int main(){
int N;
cin>>N;
vector<ll>A(N),SUM(N+1),Max(N+1);
ll sum=0;
rep(i,N){
cin>>A[i];
sum+=A[i];
SUM[i+1]=sum;
Max[i+1]=MAX(Max[i],SUM[i+1]);
}
ll ans=0,now=0;
for(int i=1;i<=N;i++){
ans=MAX(ans,now+Max[i]);
now+=SUM[i];
}
cout<<ans<<endl;
}
この記事が気に入ったらサポートをしてみませんか?