第六届河南省赛 River Crossing 简单DP-白红宇的个人博客

第六届河南省赛 River Crossing 简单DP

发布日期：2021-05-09 04:20:36 浏览次数：19 分类：博客文章

本文共 2155 字，大约阅读时间需要 7 分钟。

1488: River Crossing

Time Limit: 1 Sec

Memory Limit: 128 MB

Submit: 83

Solved: 42

Description

　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).

Input

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)

Output

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

Sample Input

2 10

5 10

100

Sample Output

思路：注意一句话，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.).

这句话有点迷。说明并没有对羊进行编号。假如第一只，第二只运过去，回来运第三只羊，花费还是按照第一只的算，以此类推。

另dp[i]为当运送第i只羊的最小花费，那么相当于它是由两种状态转移来的，一种是前i只羊一起运送，一种就是前j只羊一起运送，然后i-j到i只羊为第二批再运送一次，两者加和得到的较小值。

即dp[i]=min(dp[i],dp[i-j]+dp[j]+m)。

代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d %d",&n,&m); int dp[n+1],sum[n+1]; fill(dp,dp+n+1,0); fill(sum,sum+n+1,0); for(int i=1;i<=n;i++) { scanf("%d",&sum[i]);sum[i]+=sum[i-1]; } for(int i=1;i<=n;i++) { dp[i]=sum[i]+m; for(int j=1;j<=i;j++) { dp[i]=min(dp[i],dp[j]+dp[i-j]+m); } } printf("%d\n",dp[n]); } return 0;}

上一篇：天梯赛 L2-020. 功夫传人 BFS

下一篇：2017计蒜客蓝桥杯模拟赛5

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！