題目要求
有 n 個學(xué)生站成一排，每個學(xué)生有一個能力值，牛牛想從這 n 個學(xué)生中按照順序選取 k 名學(xué)生，
要求相鄰兩個學(xué)生的位置編號的差不超過 d，使得這 k 個學(xué)生的能力值的乘積最大，你能返回最大的乘積嗎？
題目解析
思路一：
- 分析
1、要找出n個同學(xué)里面的K個同學(xué)，而且使之能力值的乘積最大，我們可以看成先在n個同學(xué)中找到K個同學(xué)中的最后一個。
然后再在找到的同學(xué)的左邊，找出K-1個同學(xué)。并使之符合約束。
2、首先我們可以假設(shè)他找到的最后一個下標為one，而從n個數(shù)中要取得k個數(shù)的方法就有f[k][one]中，那么left為one左邊的第一個，那么
找到left的方法有f[k-1][left]種。那么有max{ k-1 , one - d} <= left <= n-1 }
3、既然n與k已經(jīng)確定，接下來只需要對數(shù)據(jù)進行遞推。
用兩個二維數(shù)組存儲當最后一個選中的值坐標為one需要選擇的為k時，其最大最小值應(yīng)該為kk[n][k] ; gg[n][k] ;
注意：要考慮正負數(shù)問題，區(qū)分當前one所在地址的值為正數(shù)還是復(fù)數(shù)。
- 代碼段
public class Text {
public static void getResult() {
int n ;
int[] arr ;
int k ;
int d ;
Scanner sc = new Scanner(System.in) ;
while(sc.hasNext()) {
n = sc.nextInt() ;
arr = new int[n+1] ;
for(int i = 1 ; i <= n ; i++ ) {
arr[i] = sc.nextInt() ;
}
k = sc.nextInt() ;
d = sc.nextInt() ;
//存儲最大值
long[][] aa = new long[k+1][n+1] ;
//存儲最小值
long[][] ll = new long[k+1][n+1] ;
//將K = 1 的情況保存
for(int one = 1 ; one <= n ; one++) {
aa[1][one] = arr[one] ;
ll[1][one] = arr[one] ;
}
long maxtemp = 0 ;
long mintemp = 0;
//從底層遞推
for(int kk = 2 ; kk <= k ; kk++ ) {
for(int one = kk ; one <= n ; one++) {
maxtemp = Long.MIN_VALUE ;
mintemp = Long.MAX_VALUE ;
//對one左邊的進行檢索，找出最大值和最小值
for(int left = one-1 ; left >= Math.max(kk-1, one-d) ; left-- ) {
if(maxtemp < Math.max(arr[one]*ll[kk-1][left], arr[one]*aa[kk-1][left])) {
maxtemp = Math.max(arr[one]*ll[kk-1][left], arr[one]*aa[kk-1][left]) ;
}
if(mintemp > Math.min(arr[one]*ll[kk-1][left], arr[one]*aa[kk-1][left])) {
mintemp = Math.min(arr[one]*ll[kk-1][left], arr[one]*aa[kk-1][left]) ;
}
}
aa[kk][one] = maxtemp ;
ll[kk][one] = mintemp ;
}
}
long result = Long.MIN_VALUE ;
for(int i = n ; i >= k ; i--) {
result = (result > aa[k][i]) ? result : aa[k][i] ;
}
System.out.println(result);
}
}
public static void main(String[] args) {
getResult();
}
}
輸入用例
3
7 4 7
2 50
輸出用例
49
感悟
這道題主要的點在我們是否能將要找出n個同學(xué)里面的K個同學(xué)，而且使之能力值的乘積最大，看成先在n個同學(xué)中找到K個同學(xué)中的最后一個。然后再在找到的同學(xué)的左邊，找出K-1個同學(xué)。并使之符合約束。從而使用動態(tài)規(guī)劃進行解析，得到結(jié)果。
（雖然很多人都知道，但總有人不知道，貼一下）
- 動態(tài)規(guī)劃基本思想：
基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復(fù)計算，節(jié)省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計算過，就將其結(jié)果填入表中。這就是動態(tài)規(guī)劃法的基本思路。
