USACO 2008 Mar Silver 3.River Crossing 动态规划水题

Code：

#include<cstring>

#include<algorithm>

#include<cstdio>

using namespace std;

const int maxn = 2500 + 4;

const int inf = 100000000;

int f[maxn], sumv[maxn];

int main()

{

    freopen("r.in","r",stdin);

    freopen("r.out","w",stdout);

    int n, m;

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

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

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

    {

        f[i] = inf;

        for(int j = 0;j < i; ++j) f[i] = min(f[i], f[j] + sumv[i - j]);

        f[i] += 2 * m;

    }

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

    fclose(stdin);

    fclose(stdout);

    return 0;

}

巴特西

USACO 2008 Mar Silver 3.River Crossing 动态规划水题

最新文章

热门文章