题目链接:http://nyoj.top/problem/716

  • 内存限制:64MB 时间限制:1000ms

题目描述:

Afandi is herding N sheep across the expanses of grassland  when he finds himself blocked by a river. A single raft is available for transportation.

Afandi knows that he must ride on the raft for all crossings, but adding sheep to the raft makes it traverse the river more slowly.

When Afandi is on the raft alone, it can cross the river in M minutes When the i sheep are added, it takes Mi minutes longer to cross the river than with i-1 sheep (i.e., total M+M1   minutes with one sheep, M+M1+M2 with two, etc.).

Determine the minimum time it takes for Afandi to get all of the sheep across the river (including time returning to get more sheep).

输入描述:

On the first line of the input is a single positive integer k, telling the number of test cases to follow. 1 ≤ k ≤ 5  Each case contains:

* Line 1: one space-separated integers: N and M (1 ≤ N ≤ 1000 , 1≤ M ≤ 500).

* Lines 2..N+1:  Line i+1 contains a single integer: Mi  (1 ≤ Mi ≤ 1000)

输出描述:

For each test case, output a line with the minimum time it takes for Afandi to get all of the sheep across the river.

样例输入:

2    
2 10   
3
5
5 10  
3
4
6
100
1

样例输出:

18
50

解题思路

用dp[i]来记录带i只羊过河的最短时间，那么dp[i]=max(dp[i],dp[j]+f[i-j]+2*m),因为要一个来回所以加2*m,但是最后一趟不用回来，故最后要减去m.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t, n, m, x, f[1005], dp[1005];
    scanf("%d", &t);
    while (t--) {
        memset(dp, 62, sizeof(dp));
        dp[0] = f[0] = 0;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &x);
            f[i] = f[i - 1] + x;
        }
        for (int i = 1; i <= n; i++)
            for (int j = 0; j < i; j++)
                dp[i] = min(dp[i], dp[j] + f[i - j] + (m << 1));
        printf("%d\n", dp[n] - m);
    }
    return 0;
}