Hatena::Grouptopcoder

tsubosakaの日記

2009-01-19

SRM 320 Div1 Medium

| 19:01

典型的DP.時間sから時間eの間に得られる最大の勝利確率をボトムアップに求めればよい.

import java.util.*;

public class ContestSchedule {
  public double expectedWinnings(String[] contests) {
    TreeSet<Long> ts = new TreeSet<Long>();
    for(String contest : contests){
      Scanner sc = new Scanner(contest);
      long start = sc.nextLong();
      long end = sc.nextLong();
      ts.add(start);
      ts.add(end);
    }
    List<Long> time = new ArrayList<Long>(ts); 
    int n = time.size();
    long dp[][] = new long[n][n];
    for(String contest : contests){
      Scanner sc = new Scanner(contest);
      long start = sc.nextLong();
      int s = Collections.binarySearch(time, start);
      long end = sc.nextLong();
      int e = Collections.binarySearch(time, end);      
      long win = sc.nextLong();
      dp[s][e] = win;
    }
    for(int l = 0 ; l < n ; l++){
      for(int s = 0 ; s < n ; s++){
        int e = s + l;
        if(e >= n)break;
        for(int m = s ; m <= e ; m++){
          dp[s][e] = Math.max(dp[s][e], dp[s][m] + dp[m][e]);
        }
      }
    }
    double res = 0.0;
    for(long d[] : dp)
      for(long l : d)
        res = Math.max(res, l);
    return res * 0.01;
  }
}

WilliamTagWilliamTag2019/02/02 11:26cialis over night
medicus group buy cialis
<a href=https://greatwinesgrandhouses.com>Cheap cialis buy online</a>
does cialis get you hard
cheapest cialis 20mg
https://kellyannehulme.com
buy cialis montreal
generic cialis in 2.5mg daily tablets
<a href=https://kellyannehulme.com>20 mg cialis</a>
lilly cialis without prescription
cialis brand name usa price
https://greatwinesgrandhouses.com

WilliamTagWilliamTag2019/02/02 11:26cialis ads
buying cialis in canada online
<a href=https://greatwinesgrandhouses.com>buy Cialis 20 mg</a>
liquid cialis does it work
cialis and avodart
https://kellyannehulme.com
what does cialis cost in mexico
cialis venezuela
<a href=https://greatwinesgrandhouses.com>Cheap cialis</a>
the cheapest cialis online
headache after cialis
https://greatwinesgrandhouses.com

ArnoldNizArnoldNiz2019/02/05 20:50canada drug generic cialis
buy generic cialis from canada
<a href="http://xcialisxx.com">Cheap Cialis</a>
snort cialis
cialis online con ricetta
<a href="http://cialistlm.com">Cheap Cialis buy</a>
brand cialis online mastercard
quick ship cialis
<a href="http://xcialisxx.com">Cheap Cialis</a>