題意：就是求用木筏把羊運(yùn)送到對(duì)岸所需時(shí)間最少

用數(shù)組 a[i] 記錄運(yùn)送 i ?只羊所需的時(shí)間

dp[i] 表示運(yùn)送i 只羊所用的最少時(shí)間

代碼：

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int dp[1005]; int a[1005] = {0}; int main() {int t,n,m,x;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++){scanf("%d",&x);a[i] = a[i-1] + x;}for(int i = 1;i <= n;i++){dp[i] = a[i] + m;//當(dāng)前運(yùn)送i只羊過(guò)河所要花費(fèi)的時(shí)間for(int j = 1;j < i;j++){dp[i] = min(dp[i],dp[i-j]+dp[j]+m);//先運(yùn)送j只羊返回再運(yùn)送i-j只羊的花費(fèi)時(shí)間與當(dāng)前運(yùn)送i只羊相比的最小值}}printf("%d\n",dp[n]);} }

總結(jié)

以上是生活随笔為你收集整理的nyoj-716 River Crossing（动态规划）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。