nyoj716 River Crossing 简单DP 01串 省六

描述

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
355 10
3461001

样例输出

1850

来源

第六届河南省程序设计大赛

上传者

#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[1005];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m,temp;
scanf("%d%d",&n,&m);
dp[0]=m;
for(int i=1;i<=n;i++)
{
scanf("%d",&temp);
dp[i]=dp[i-1]+temp;
}
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
dp[i]=min(dp[i],dp[i-j]+dp[j]+m);
printf("%dn",dp[n]);
}
return 0;
}

最后

以上就是甜美电灯胆为你收集整理的nyoj716 River Crossing 简单DP 01串 省六的全部内容，希望文章能够帮你解决nyoj716 River Crossing 简单DP 01串 省六所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。