首页 > 代码库 > BZOJ 1617 渡河问题

BZOJ 1617 渡河问题

普及组dp。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 2550#define inf 2147483647using namespace std;int n,m,tab[maxn],dp[maxn];int main(){    scanf("%d%d",&n,&m);    for (int i=1;i<=n;i++) scanf("%d",&tab[i]);    for (int i=2;i<=n;i++) tab[i]+=tab[i-1];    for (int i=1;i<=n;i++) dp[i]=inf;    for (int i=1;i<=n;i++)    {        dp[i]=tab[i]+m;        for (int j=1;j<=i-1;j++)            dp[i]=min(dp[j]+tab[i-j]+m,dp[i]);        dp[i]+=m;    }    printf("%d\n",dp[n]-m);    return 0;}

 

BZOJ 1617 渡河问题