UVa 1632 阿里巴巴（区间DP）

https://vjudge.net/problem/UVA-1632

题意：

直线上有n个点，其中第i个点的坐标是xi，且它会在di秒之后消失。Alibaba可以从任意位置出发，求访问完所有点的最短时间。

 

思路：

区间DP。

d[i][j][0]用来表示访问完区间 i ~ j 之间所有点的最短时间，并且此时处于 i 点，相反的，d[i][j][1]表示的是处于 j 点。

1 #include<iostream> 2 #include<string> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 const int maxn = 10000 + 5; 8 const int INF = 10000000; 9 10 int a[maxn], b[maxn]; 11 int n; 12 int d[maxn][maxn][2]; 13 14 int main() 15 {17 while (cin >> n) 18 { 19 memset(d, 0, sizeof(d)); 20 for (int i = 1; i <= n; i++) 21 cin >> a[i] >> b[i]; 22 for (int i = n; i >=1; i--) 23 { 24 for (int j = i + 1; j <= n; j++) 25 { 26 d[i][j][0] = min(d[i + 1][j][0] + a[i + 1] - a[i], d[i + 1][j][1] + a[j] - a[i]); 27 if (d[i][j][0] >= b[i]) d[i][j][0] = INF; 28 d[i][j][1] = min(d[i][j-1][1] + a[j] - a[j - 1], d[i][j - 1][0] + a[j] - a[i]); 29 if (d[i][j][1] >= b[j]) d[i][j][1] = INF; 30 } 31 } 32 int ans = min(d[1][n][0], d[1][n][1]); 33 if (ans == INF) puts("No solution"); 34 else printf("%d\n", ans); 35 } 36 return 0; 37 }

 

转载于:https://www.cnblogs.com/zyb993963526/p/6381886.html

总结

以上是生活随笔为你收集整理的UVa 1632 阿里巴巴（区间DP）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。