USACO MAR08 Silver River Crossing 奶牛渡河問題
本文正體字版由OpenCC轉換
初看是個數學問題，像是線性規劃求最優值的問題。其實還是動態規劃問題。
首先要算出一次載不同數量的牛過河需要的時間，就是數據給出的序列求前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