題意：求兩個(gè)車站之間的最小費(fèi)用。

解題思路：這道題本來應(yīng)該是屬于線段樹優(yōu)化的dp問題，但是數(shù)據(jù)太水了，所以O(shè)(n2)的復(fù)雜度也過了。主要是線段樹的話難得打，所以就直接用暴力破了。這里有個(gè)坑：a可能大于b。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 10005; const int inf = 1e9+10; int L1,L2,L3,C1,C2,C3; int n,a,b,dis[maxn],dp[maxn];int main() {while(scanf("%d%d%d%d%d%d",&L1,&L2,&L3,&C1,&C2,&C3)!=EOF){scanf("%d%d%d",&n,&a,&b);if(a > b) swap(a,b);for(int i = 2; i <= n; i++)scanf("%d",&dis[i]);for(int i = a; i <= b; i++) dp[i] = inf;dp[a] = 0;for(int i = a + 1; i <= b; i++)for(int j = i - 1; j >= 1; j--){if(dis[i] - dis[j] <= L1)dp[i] = min(dp[i],dp[j] + C1);else if(dis[i] - dis[j] <= L2)dp[i] = min(dp[i],dp[j] + C2);else if(dis[i] - dis[j] <= L3)dp[i] = min(dp[i],dp[j] + C3);else break;}printf("%d\n",dp[b]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的poj 2355(简单dp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。