地铁建设_纪中2568_dp

Description

某地铁沿线共设N站，可分为U（地面式）、D（地下式）和C（复合式）三种类型。为避免单调，相邻地铁站的类型不能重复。同时，由于地铁站所处环境和地质条件有所差异，每个站点按不同类型的建设成本也不尽相同。现给定各站点的三种建设成本，请计算出该地铁线的最低总造价。

Input

输入文件subway.in包含N+1行：
第1行为一个正整数，表示地铁站的总数N。
第2行到第N+1行分别包含用空格分隔的三个正整数U，D和C。其中第i+1行表示第i个地铁站按U、D 或C 类型的建设成本，1≤i≤N。

Output

输出文件subway.out只包含一个正整数，表示建成这N个地铁站所需要的最低成本。

Hint

对于20%的数据，N≤10；
对于40%的数据，N≤1000；
对于100%的数据，N≤200000，1≤U, D, C≤10000

题解

状态只有三种直接推，这dp要多暴力有多暴力
f[i][j]=min(f[i−1][k]+v[j])   (j≠k)
第一维可以滚

Code

#include 
using namespace std;
int v[201001][3],f[2][3];
int min(int x,int y){return xint main()
{int n;scanf("%d",&n);for (int i=1;i<=n;i++)for (int j=0;j<3;j++)scanf("%d",&v[i][j]);int x=1;f[1][0]=v[1][0];f[1][1]=v[1][1];f[1][2]=v[1][2];for (int i=2;i<=n;i++){x=x^1;for (int j=0;j<3;j++)f[x][j]=1<<31-1;for (int j=0;j<3;j++)for (int k=0;k<3;k++)if (j!=k)f[x][j]=min(f[x^1][k]+v[i][j],f[x][j]);}int ans=1<<31-1;for (int i=0;i<3;i++)if (f[x][i]printf("%d\n",ans);return 0;
}

转载于:https://www.cnblogs.com/olahiuj/p/5781201.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！