HDU-2182 Forg 動態規劃DP 題解

Problem Description

A little frog named Fog is on his way home. The path’s length is N (1 <= N <= 100), and there are many insects along the way. Suppose the
original coordinate of Fog is 0. Fog can stay still or jump forward T units, A <= T <= B. Fog will eat up all the insects wherever he stays, but he will
get tired after K jumps and can not jump any more. The number of insects (always less than 10000) in each position of the path is given.
How many insects can Fog eat at most?
Note that Fog can only jump within the range [0, N), and whenever he jumps, his coordinate increases.

Input

The input consists of several test cases.
The first line contains an integer T indicating the number of test cases.
For each test case:
The first line contains four integers N, A, B(1 <= A <= B <= N), K (K >= 1).
The next line contains N integers, describing the number of insects in each position of the path.

Output

each test case:
Output one line containing an integer - the maximal number of insects that Fog can eat.

Sample Input

1
4 1 2 2 
1 2 3 4 

Sample Output

8

題目翻譯

Problem Description

一只名叫Frog的大蛤蟆正在回家的路上，這條路的長度是N（1<=N<=100），沿途有許多昆蟲，假設Frog的原始坐標為0，Frog可以保持靜止或向前跳躍T單位，A<=T<=B，無論他呆在哪里，Frog都會吃掉所有的昆蟲，但他會的K跳后累了，不能再跳了，給出了路徑中每個位置的昆蟲數量（始終小于10000），Frog最多能吃多少昆蟲？

請注意，Forg只能在[0，N]范圍內跳躍，每當他跳躍時，他的坐標就會增加.

Input

輸入由幾個測驗用例組成，
第一行包含一個整數T，表示測驗用例的數量，
對于每個測驗用例：
第一行包含四個整數N，A，B（1<=A<=B<=N），K（K>=1），
下一行包含N個整數，描述路徑中每個位置的蟲子數量，

Output

對于每組測驗樣例，輸出一行，包含一個整數，表示Fog能吃到蟲子數量的最大值

題目分析

這真的是DP大水題了，打個二維滾動陣列就出來了，

青蛙在長度為N的道路上跳K次，每次跳的單位為T，在這里插一句，如果這個T為1，那么這題就是一個0-1背包了…

首先，設 d p [ i ] [ j ] dp[i][j] dp[i][j]表示Fog跳 j j j次到達 i i i坐標處可以吃到的最多的蟲子數，那么狀態轉移方程：

d p [ i ] [ j ] = m a x ( d p [ i ] [ j ] , d p [ t ] [ j ? 1 ] + a r r [ i ] ) dp[i][j]=max(dp[i][j],dp[t][j-1]+arr[i]) dp[i][j]=max(dp[i][j],dp[t][j?1]+arr[i])

記得在最后答案里加上初始位置的蟲子數，我們從初始位置開始滾動時是無法將初始位置的昆蟲數目加入dp陣列的

AC Code

#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int arr[N], dp[N][N];

int main(){
    ios::sync_with_stdio(0);
    int t = 0; cin >> t;
    while(t--){
        int n, a, b, k; cin >> n >> a >> b >> k;
        for(int i = 1; i <= n; i++) cin >> arr[i];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= k; j++){
                for(int k = i + a; k <= i + b && k <= n; k++){			//列舉跳到的位置
                    dp[k][j] = max(dp[k][j], dp[i][j - 1] + arr[k]);
                }
            }
        }
        cout << dp[n][k] + arr[1] << endl;
    }
    return 0;
}