洛谷 P2904 [USACO08MAR]跨河River Crossing

动规方程 f[i]=min(f[i],f[i−j]+sum)

我们默认为新加一头牛，自占一条船。想象一下，它不断招呼前面的牛，邀请它们坐自己这条船，当且仅当所需总时间更短时，前一头奶牛会接受邀请，最多邀请前面的所有奶牛一起坐这条船。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 const int maxn=;

 int n,m,mt[maxn],f[maxn];

 int main(){

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++)scanf("%d",&mt[i]);

     memset(f,,sizeof(f));

     f[]=;

     for(int i=;i<=n;i++){

         int sum=*m;

         for(int j=;j<=i;j++){

             sum+=mt[j];

             f[i]=min(f[i],f[i-j]+sum);

         }

     }

     printf("%d",f[n]-m);

     return ;

 }