Topcoder筋トレ: 筋トレ7日目: SRM565 Div1Easy "MonstersValley"

2013年6月12日水曜日

■時間
25分

■問題 SRM565 Div1 Easy "MonstersValley"

各地点i（1<=t<=T）におけるモンスターの強さdread[i]と、買収した場合の値段price[i]（price[i]∈{1,2}）があった場合に、1からTまで無事に通過するための最小の値段を返せ。

ただし、強さdread[i]のモンスターに遭遇した時は、それまでに買収したモンスターの合計以下の強さの場合は素通り出来る（買収もできる）。合計より強い場合は買収しないといけない。

尚dreadは1〜10^12、Tは1〜50。

■試した解き方

Tが大きいためbrute forceは当然無理。

priceが1か2しかないことに着目。最大でもT*2しか払わなくていいということ。

各地点iにおいて、各今まで払った額p[i]毎に、仲間モンスターの一番高い強さを計算していけばO(T^2)で解ける

 public int minimumPrice(long[] dread, int[] prices) {

  int maxPrice=dread.length*2;

  Long largestTotalFor[][]=new Long[dread.length][maxPrice+1];

  largestTotalFor[0][prices[0]]=dread[0];

  for(int i=1;i<dread.length;i++){

   int priceForI=prices[i];

   for(int price=0;price<=maxPrice;price++){

    Long total=null;

    //buy?

    if(price-priceForI>=0 && largestTotalFor[i-1][price-priceForI]!=null)

     total=largestTotalFor[i-1][price-priceForI]+dread[i];

    //walk through?

    if(largestTotalFor[i-1][price]!=null && largestTotalFor[i-1][price]>=dread[i])

     if(total==null || largestTotalFor[i-1][price]>total)

      total=largestTotalFor[i-1][price];

    largestTotalFor[i][price]=total;

}

}

  for(int i=0;i<=maxPrice;i++)

   if(largestTotalFor[dread.length-1][i]!=null)

    return i;

  return 0;

}

1st submit:
OK

■Editorial
同じ解き方。

■反省

・苦手なdynamic programming系の問題を解けて満足。

■筋トレ記録
勝率57% (4/7)

Topcoder筋トレ