UVA 1336 Fixing the Great Wall——dp

UVA 1336 Fixing the Great Wall——dp

从紫书前面做过来的话就知道是老思路了，额外加个累计数组就好，另外精度卡的不是很严格，写起来可以随意一些

#include #include #include #include using namespace std;const int maxn = 1010;const int INF = 0x3f3f3f3f;int n, v, X, p[maxn], sum[maxn][maxn][2];double dp[maxn][maxn][2];struct Node { int x, c, t; bool operator < (const Node &no) const { return x < no.x; }}node[maxn];void init() { sort(node+1,node+1+n); int s = 0; for (int i = 1; i <= n; i++) s += node[i].t, p[i] = node[i].x; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) dp[i][j][0]=dp[i][j][1]=INF; int pos = lower_bound(p+1,p+1+n,X)-p; if (node[pos].x == X) { dp[pos][pos][0]=dp[pos][pos][1]=node[pos].c; sum[pos][pos][0]=sum[pos][pos][1]=s-node[pos].t; } else { dp[pos][pos][0]=dp[pos][pos][1]=1.0*(node[pos].x-X)/v*s+node[pos].c; sum[pos][pos][0]=sum[pos][pos][1]=s-node[pos].t; if (pos-1>=1) { pos--; dp[pos][pos][0]=dp[pos][pos][1]=1.0*(X-node[pos].x)/v*s+node[pos].c; sum[pos][pos][0]=sum[pos][pos][1]=s-node[pos].t; } }}void update(int x1,int x2,int x3,int y1,int y2,int y3,int c1,double c2,int c3) { if (dp[x1][x2][x3] > dp[y1][y2][y3]+c1+c2) { dp[x1][x2][x3] = dp[y1][y2][y3]+c1+c2; sum[x1][x2][x3] = sum[y1][y2][y3]-c3; }// else if (dp[x1][x2][x3] == dp[y1][y2][y3]+c1+c2) {// sum[x1][x2][x3] = min(sum[x1][x2][x3],sum[y1][y2][y3]-c3);// }}int main() { while (~scanf("%d%d%d",&n,&v,&X)&&n+X+v) { for (int i = 1; i <= n; i++) scanf("%d%d%d",&node[i].x,&node[i].c,&node[i].t); init(); for (int len = 1; len < n; len++) { for (int i = 1; i + len - 1 <= n; i++) { int j = i+len-1; double cost = 0.0; if (dp[i][j][0] != INF) { if (i-1 >= 1) { cost = 1.0*(node[i].x-node[i-1].x)/v*sum[i][j][0]; update(i-1,j,0,i,j,0,node[i-1].c,cost,node[i-1].t); } if (j+1 <= n) { cost = 1.0*(node[j+1].x-node[i].x)/v*sum[i][j][0]; update(i,j+1,1,i,j,0,node[j+1].c,cost,node[j+1].t); } } if (dp[i][j][1] != INF) { if (i-1 >= 1) { cost = 1.0*(node[j].x-node[i-1].x)/v*sum[i][j][1]; update(i-1,j,0,i,j,1,node[i-1].c,cost,node[i-1].t); } if (j+1 <= n) { cost = 1.0*(node[j+1].x-node[j].x)/v*sum[i][j][1]; update(i,j+1,1,i,j,1,node[j+1].c,cost,node[j+1].t); } } } } printf("%d\n", (int)min(dp[1][n][0],dp[1][n][1])); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。