|
上記の考え方をそのまま実装してみたところコード実行速度5位メモリ使用量低で正答できました。
ここから先の高速化とかはあまり考えてないので。
もし高速化できそうなところがあったらご指摘ください。
#include<stdio.h>
#include<string.h>
const int A=0;//二人をAさんBさんとする
const int B=1;
void setData(int n){
int memo[2][5002];//[次にもらうのがAさん=0 Bさん=1][Aさんがここまででもらった個数]=最小切断時間
int next[2][5002];//次の切断箇所の検討
int cutTimes[10001];//切断時間
int cutTime,herf=n/2,nowTime;
int up;
for(int i=0;i<n-1;i++)scanf("%d",&cutTimes[i]);
memset(memo,127,sizeof(memo));//足される切断秒数は10000なのでオーバーフローしない
memo[A][1]=0;//計算しやすいようAさんが1個目を取得した状態から始める
for(int turn=0;turn<n-1;turn++){
memset(next,127,sizeof(next));//ダミーデータ
cutTime=cutTimes[turn];//切断箇所をずらしていく
up=turn+1>herf?herf:turn+1;//上限
for(int k=1;k<=up;k++){
nowTime=memo[A][k];//Aさん
//切断せずAさんが続けてもらう
next[A][k+1]=nowTime;
//切断して次はBさんがもらう
next[B][k]=nowTime+cutTime;
}
for(int k=1;k<=up;k++){
//Bさんの番
nowTime=memo[B][k];
//Bさんが続けてもらう
next[B][k]=next[B][k]>nowTime?nowTime:next[B][k];
//Aさんがもらう
nowTime+=cutTime;
next[A][k+1]=next[A][k+1]>nowTime?nowTime:next[A][k+1];
}
memcpy(memo,next,sizeof(next));
}
nowTime=memo[A][herf]>memo[B][herf]?memo[B][herf]:memo[A][herf];
printf("%d\n",nowTime);
}
int main(){
int n;
scanf("%d",&n);
setData(n);
while(scanf("%d",&n)!=EOF){
}
}
|