P2904 [USACO08MAR] River Crossing S
题目描述
农夫约翰以及他的 \(N(1 \le N \le 2500)\) 头奶牛打算过一条河，但他们所有的渡河工具，仅仅是一个木筏。
由于奶牛不会划船，在整个渡河过程中，约翰必须始终在木筏上。在这个基础上，木筏上的奶牛数目每增加 \(1\)，FJ把木筏划到对岸就得花更多的时间。
当约翰一个人坐在木筏上，他把木筏划到对岸需要 \(M(1 \le M \le 1000)\) 分钟。当木筏搭载的奶牛数目从 \(i-1\) 增加到 \(i\) 时，约翰得多花 \(M_i(1 \le M_i \le 1000)\) 分钟才能把木筏划过河（也就是说，船上有 \(1\) 头奶牛时，约翰得花 \(M+M_1\) 分钟渡河；船上有 \(2\) 头奶牛时，时间就变成 \(M+M_1+M_2\) 分钟。后面的以此类推）。那么，约翰最少要花多少时间，才能把所有奶牛带到对岸呢？当然，这个时间得包括约翰一个人把木筏从对岸划回来接下一批的奶牛的时间。
输入格式
- 第一行包含 \(2\) 个整数 \(N\) 和 \(M\)。
- 第 \(2\) 行至第 \(N + 1\) 行，其中第 \(i + 1\) 行包含 \(1\) 个整数 \(M_i\)。
输出格式
- 输出共 \(1\) 行，为农夫约翰让所有奶牛过河所需的最短时间。
输入输出样例 #1
输入 #1
5 10
3
4
6
100
1 输出 #1
50 说明/提示
有五头牛，农夫约翰独自过河需要 \(10\) 分钟，带一头牛需要 \(13\) 分钟，带两头牛需要 \(17\) 分钟，带三头牛需要 \(23\) 分钟，带四头牛需要 \(123\) 分钟，带五头牛需要 \(124\) 分钟。
农夫约翰可以先带三头牛过河（\(23\) 分钟），然后独自返回（\(10\) 分钟），再带最后两头牛过河（\(17\) 分钟）。总共耗时 \(23+10+17=50\) 分钟。
解题思路：当我们把n看出一个背包的容量，运i头牛需要\(m_{i}\)的时间，把i看成物品的体积，\(m_{i}\)看成价值，那么这就是一个01背包问题。
//转换为01背包和完全背包求解，速度最快，复杂度O(V*Σlog n[i])
#include <bits/stdc++.h>
using namespace std;
int n,v,dp[50001]; //物品数量和背包容量
int m,ans=1e9+9;
int i,j,k,w[50001],p[50001],c[50001];
int main()
{cin>>n>>m;w[0]=m;for(i=1;i<=n;i++) {cin>>p[i];w[i]=w[i-1]+p[i];}// for (int i = 1; i <= n; i++) dp[i] = 1000000000;// dp[1] = dp[0] + w[1] + m;for (int i = 1; i <= n; i++) dp[i]=w[i]+m;;for(i=2;i<=n;i++) {for(j=0;j<=i-1;j++) {dp[i]=min(dp[i],dp[j]+w[i-j]+m);}}cout<<dp[n]-m<<endl;return 0;
}