题目
动规方程 f[i]=min(f[i],f[i?j]+sum)
我们默认为新加一头牛, 自占一条船想象一下, 它不断招呼前面的牛, 邀请它们坐自己这条船, 当且仅当所需总时间更短时, 前一头奶牛会接受邀请, 最多邀请前面的所有奶牛一起坐这条船
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- using namespace std;
- const int maxn=2505;
- int n,m,mt[maxn],f[maxn];
- int main(){
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++)scanf("%d",&mt[i]);
- memset(f,101,sizeof(f));
- f[0]=0;
- for(int i=1;i<=n;i++){
- int sum=2*m;
- for(int j=1;j<=i;j++){
- sum+=mt[j];
- f[i]=min(f[i],f[i-j]+sum);
- }
- }
- printf("%d",f[n]-m);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2521638.html