首页 > 代码库 > 洛谷P2904 [USACO08MAR]跨河River Crossing 动态规划
洛谷P2904 [USACO08MAR]跨河River Crossing 动态规划
洛谷P2904 [USACO08MAR]跨河River Crossing
动态规划 区间DP
f[ i ] 表示 将 i 头牛 运了过去,然后John 又返回所需要的最少时间
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <cstdlib> 5 #include <string> 6 #include <algorithm> 7 #include <iomanip> 8 #include <iostream> 9 using namespace std ; 10 11 const int maxn = 2501,inf = 1e9 ; 12 int n,m ; 13 int f[maxn],cost[maxn] ; 14 15 inline int read() 16 { 17 char ch = getchar() ; 18 int x = 0 ,f = 1 ; 19 while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f = -1 ;ch = getchar() ; } 20 while(ch>=‘0‘&&ch<=‘9‘) { x = x*10+ch-48 ; ch = getchar() ; } 21 return x * f ; 22 } 23 24 int main() 25 { 26 n = read() ; m = read() ; 27 cost[ 0 ] = 2*m ; 28 for(int i=1;i<=n;i++) cost[ i ] = cost[i-1] + read() ; 29 // cost[ i ] 表示一次将 i 个人送到对面再回来所需要的时间 30 31 for(int i=0;i<=n;i++) f[ i ] = inf ; 32 f[ 0 ] = 0 ; 33 34 35 for(int i=1;i<=n;i++) 36 for (int j=0;j<i;j++) 37 f[ i ] = min(f[ i ],f[ j ] + cost[ i-j ] ) ; 38 printf("%d\n",f[ n ]-m) ; 39 40 return 0 ; 41 }
洛谷P2904 [USACO08MAR]跨河River Crossing 动态规划
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。