d918. 6. 雨量趨勢
內容 ：
台灣近年來經常豪雨成災。每遇有豪雨，新聞記者就將以往降雨紀錄拿出，並以聳動字眼云之，如「30 年來最大降雨量」、「40 年
來首見」等。李先生是一位科學家，認為用直覺讀取數據容易造成偏頗，他想用更科學的方式來解讀降雨量，希望能找出降雨量長期趨勢。在觀察一連串的降雨量數
據後，李先生想找出最長的遞增序列，以代表長期趨勢。在他所找到的長期趨勢資料中，一般而言是逐步上升，但某次破紀錄的最大雨量之後，若有稍大雨量
(雖未破紀錄)，亦視為遞增序列之內容。換言之，他欲找出最長近乎遞增序列。
舉例來說，李先生的雨量數據有12 個，如下：'
9, 15, 3, 14, 14, 8, 10, 11, 17, 15, 14, 13
另外設定一個 E 值，代表稍大雨量與長期趨勢目前最大雨量可以允許的差值。假設 E = 1，則可以找出下列五組最長近乎遞增序列，其長度均為 6 :
(9, 15, 14, 14, 15, 14), (9, 8, 10, 11, 15, 14), (3, 8, 10, 11, 15, 14), (9, 8, 10, 11, 14, 13), (3, 8, 10, 11, 14, 13)
又若 E = 0，則最長近乎遞增序列有四組 (3, 8, 10, 11, 13), (3, 8, 10, 11, 14), (3, 8, 10, 11, 15), (3, 8, 10, 11, 17)，其長度均為 5 。
再看另一個例子，假設雨量數據為 3, 4, 4, 6, 5, 4。若 E = 0，則有三組最長近乎遞增序列：(3, 4, 4, 6) , (3, 4, 4, 5), (3, 4, 4, 4)，長度均為 4。若 E = l，則有二組：(3, 4, 4, 6, 5), (3, 4, 4, 5, 4)。若 E = 2，則有一組：(3, 4, 4, 6, 5, 4)。本題的答案只要輸出長度即可。
輸入說明
：
輸出說明
：
範例輸入 ：
輸入範例 1: 12 3 9 15 3 14 14 8 10 11 17 15 14 13 0 1 999990 輸入範例 2: 4 3 1 0 999900 999800 1000 0 l
範例輸出 ：
輸出範例 1: 5 6 12 輸出範例2 : 4 2 3
提示
：
出處
：
作法 : O(n^2) LIS 的變形
DP[j] = max(DP[i], DP[j]+tmp+1) when i < j, 其中 tmp = A[i]~A[j] 中, 範圍介於
A[i]-E~A[i]-1 的個數
/**********************************************************************************/
/* Problem: d918 "6. 雨量趨勢" from 99資訊能力競賽全國決賽 */
/* Language: C (743 Bytes) */
/* Result: AC(40ms, 317KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-11-04 17:24:47 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int A[3500];
int Approximate_LIS(int E, int n) {
int Ans = 0, i, j, tmp, DP[3500], max;
memset(DP, 0, sizeof(DP));
for(i = 0; i < n; i++) {
tmp = 0, max = 0;
for(j = i+1; j < n; j++) {
if(A[i]-E <= A[j] && A[j] < A[i])
tmp++;
if(A[i] <= A[j])
DP[j] = DP[j] > DP[i]+tmp+1 ? DP[j] : (DP[i]+tmp+1);
max = max > DP[j] ? max : DP[j];
}
Ans = Ans > DP[i]+tmp ? Ans : DP[i]+tmp;
}
return Ans+1;
}
main() {
int n, m, i, E;
while(scanf("%d %d", &n, &m) == 2) {
for(i = 0; i < n; i++)
scanf("%d", &A[i]);
for(i = 0; i < m; i++) {
scanf("%d", &E);
printf("%d ", Approximate_LIS(E, n));
}
puts("");
}
return 0;
}