TopCoder SRM 487

SRM 487(11/14 2:00~4:00)

悪夢再び…．

■BunnyComputer(Div1 Easy)

コンピュータのスケジューリングを考える問題．詳細は本家サイトを御参照下さい…．

0，…，kのそれぞれはどう選んでも干渉しないので，それぞれにおいて適当に判定すれば大丈夫，とか思いましたが，ちゃんとDPで最大値を計算しないとダメでした…．

wataさんのコードを参考にしたコードはこちら．

view plainprint?

1. public class BunnyComputer{  
2.  public int getMaximum(int[] pre, int k){  
3.   int n=pre.length;  
4.   int res=0;  
5.   for(int j=0;j<k+1;j++){  
6.    int dp1=0, dp2=0;  
7.    for(int i=j;i+k+1<n;i+=k+1){  
8.     int a1=Math.max(dp1,dp2);  
9.     int a2=dp1+pre[i]+pre[i+k+1];  
10.     dp1=a1;  
11.     dp2=a2;  
12.    }  
13.    res+=Math.max(dp1,dp2);  
14.   }  
15.   return res;  
16.  }  
17. }  

public class BunnyComputer{
 public int getMaximum(int[] pre, int k){
  int n=pre.length;
  int res=0;
  for(int j=0;j<k+1;j++){
   int dp1=0, dp2=0;
   for(int i=j;i+k+1<n;i+=k+1){
    int a1=Math.max(dp1,dp2);
    int a2=dp1+pre[i]+pre[i+k+1];
    dp1=a1;
    dp2=a2;
   }
   res+=Math.max(dp1,dp2);
  }
  return res;
 }
}

仮にk=0，preference={3,1,4,1,5,9,2,6}とします．
隣り合う2項を足し合わせれば，
a={4,5,5,6,14,11,8}
となります．言い換えれば，「数列aより，隣り合う2項を選ばないように抽出した項の総和を最大にしたい」という事ですので，これはシンプルなDPとなるのです．

■Challenge
撃墜しようとしたらされて…．

■Result
××× 0 0
0.0p

■Rating
1399 -> 1348

2連続減少．実に良くないですねえ．