阿祁的部落格

ZeroJudge c528-相隔小於一定距離最小總和子序列 解題心得( 題目 )

解題概念:DP

解題方法:一開始我們先定義dp[i]，代表到第i格(含)以前，有拿第i格的最小總和，而dp轉移式為dp[i]=min(dp[i-k],...,dp[i-2],dp[i-1])，如果這樣，那題目可以變成輸出dp[n](我們假設最後一個數後面還有一個0，就可以得到n+1個數字之間的最小總和)，但是每次的dp轉移需要重複判斷取最小，時間複雜度為O(nk)，如果n、k很大一定爆炸，所以我們實作一個物件pair(x,y)，x代表他的值、y代表他的座標+k(dp的選取範圍)，將他放進一個PriorityQueue(照x大小排序)，每次dp從裡面poll一個出來，如果不在範圍內就繼續poll，最後就可以得到答案。

參考程式碼( 如果有更好意見可在下方留言，以做為本文章之補充，感謝! ):

//Author:欉恩祁

import java.io.*;

import java.util.*;

public class zjc528 {

   public static int ret,r,minus;
 
   public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
 
   public static void main(String[] args) throws Exception {
 
       PriorityQueue<pair> dp=new PriorityQueue<>(new Comparator<pair>() {
 
           //Override
 
           public int compare(pair f,pair s) {
 
               if(s.x<=f.x)return 1;
 
               return -1;
 
           }
 
       }) ;
 
       final int n=rint();
 
       final int k=rint();
 
       dp.offer(new pair(0,k-1));//Initialize
 
       pair p;
 
       for(int i=0;i<n;i++) {
 
           p=dp.poll();
 
           while(p.y<i) {//not in range
 
               p=dp.poll();
 
           }
 
           dp.offer(p);
 
           dp.offer(new pair(p.x+rint(),i+k));//new dp
 
       }
 
       p=dp.poll();
 
       while(p.y<n) {
 
           p=dp.poll();
 
       }
 
       System.out.println(p.x);
 
   }
 
   public static int rint() throws Exception {
 
       //輸入
 
       ret=0;
 
       r=br.read();
 
       minus=1;
 
       if(r==(int)'-') { //負值
 
           minus=-1;
 
           r=br.read();
 
       }
 
       while(r>47&&r<58) {
 
           ret*=10;
 
           ret+=(r&15);
 
           r=br.read();
 
       }
 
       return ret*minus;
 
   }


}



class pair{

   int y;
 
   long x;
 
   //x->dp sum
 
   //y->range

    pair(long a,int b){
 
       x=a;

       y=b;
 
   }
}