Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2339-78e47cd5
この記事にトラックバックする(FC2ブログユーザー)

Bayan 2012-2013 Elimination Round A問題 - Build String (この記事を編集する[管理者用])

Source

Bayan 2012-2013 Elimination Round A問題 (ACM/ICPC形式)
Problem description

問題概要

n個の都市が一直線上に並んでいる.左から番号1~n.nは1000以下.
車で,番号1の都市から,番号nの都市に移動したい.最短時間を求める問題.
各都市間の距離d[i]と,その都市ですぐ用意できる燃料s[i]が与えられる.
都市jについた時,その瞬間燃料s[j]だけもらえる.
また,都市についた後,時間kだけ待つたびに,燃料s[j]ずつもらうこともできる.(kは都市によらず一定)
最初は,都市1についたばかりで,燃焼s[1]だけもっている.
燃料タンクは無限に燃料が入る.
距離1移動するのに,燃料1消費する.

解法

とりあえず,移動出来るだけ移動しておいて,燃料が足りなくなったら,
今まで訪れた都市の中で,最もたくさん燃料が貰える場所でkだけ待ったことにする.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int main(){
  int i,j,k,l,m,n;
  int d[2000], s[2000], mx[2000];
  int res = 0, f = 0;

  scanf("%d%d",&n,&k);
  rep(i,n) scanf("%d",d+i);
  rep(i,n) scanf("%d",s+i);

  mx[0] = s[0];
  REP(i,1,n){
    mx[i] = s[i];
    if(mx[i] < mx[i-1]) mx[i] = mx[i-1];
  }

  rep(i,n){
    f += s[i];
    while(f < d[i]) f += mx[i], res += k;
    res += d[i];
    f -= d[i];
  }

  printf("%d\n",res);

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2339-78e47cd5
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。