USACO MAR08 Silver River Crossing 奶牛渡河问题
初看是个数学问题，像是线性规划求最优值的问题。其实还是动态规划问题。
首先要算出一次载不同数量的牛过河需要的时间，就是数据给出的序列求前n项的和。设F[i]为带i头牛过河并空载回来所需要的最少时间。最后结果就是F[N]-空载的时间。
状态
* F[i] 带i头牛过河并空载回来所需要的最少时间
* G[i] 一次带i头牛过河所需要的时间
状态转移方程
* F[i]=min{ F[k] + G[i-k] } (0<=k<=i-1)
边界条件
* F[1]=G[1]+G[0];
目标结果 F[N]-G[0]
/*
ID: cmykrgb1
PROG: river
LANG: C++
*/
#include <iostream>
#define MAX 2501
using namespace std;
int N,Ans;
int M,F[MAX],G[MAX];
void init()
{
int i;
freopen("river.in","r",stdin);
freopen("river.out","w",stdout);
cin >> N >> G[0];
for (i=1;i<=N;i++)
{
cin >> M;
G[i]=G[i-1]+M;
}
}
void dynamic()
{
int i,k,min;
F[1]=G[1]+G[0];
for (i=2;i<=N;i++)
{
min=0x7FFFFFFF;
for (k=0;k<=i-1;k++)
{
if (F[k]+G[i-k]+G[0]<min)
min=F[k]+G[i-k]+G[0];
}
F[i]=min;
}
Ans=F[N]-G[0];
}
int main()
{
init();
dynamic();
cout << Ans << endl;
return 0;
}
上次修改时间 2017-02-03