Help Jimmy POJ - 1661

題意：

場景中包括多個長度和高度各不相同的平臺。地面是最低的平臺，高度為零，長度無限。

Jimmy老鼠在時刻0從高于所有平臺的某處開始下落，它的下落速度始終為1米/秒。當Jimmy落到某個平臺上時，游戲者選擇讓它向左還是向右跑，它跑動的速度也是1米/秒。當Jimmy跑到平臺的邊緣時，開始繼續下落。Jimmy每次下落的高度不能超過MAX米，不然就會摔死，游戲也會結束。

設計一個程序，計算Jimmy到底地面時可能的最早時間。

題解：

設dp[i][0]:表示到第i個板子上的左側所花時間
dp[i][1]：表示到第i個板子上的右側所花時間
從第j個到第i個平臺上，第j的高度要大于i(高度差不能超過MAX)，從j下來分左右兩個端點，需要保證左右端點都在i平臺的范圍內(這樣才能落在平臺上)，且注意，滿足上面兩個情況仍然不足，因為有可能j被k擋住了，從j就無法到i上面，一個平臺最多只能到達另一個平臺，所以我們用數組st[j][0/1]表示從平臺j出發，從左/右端點掉下去會到哪個板子，如果st = -1說明可以直接掉到當前平臺
詳細看代碼

代碼：

#include<iostream> #include<cstring> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; const int N=1010; int n,m,t,x,y,st[N][2];//st[i][0]標記第i塊板子左端可以落到那個板子，st[i][1]就是右端 struct node {int l,r,h; }e[N]; ll f[N][2]; bool cmp(node a,node b) {if(a.h==b.h) return a.l<b.l;//這里其實無所謂加不加return a.h>b.h; } int main() {cin>>t;while(t--){cin>>n>>x>>y>>m;for(int i=1;i<=n;i++){int a,b,c;cin>>a>>b>>c;e[i]={a,b,c};}e[0]={x,x,y};sort(e+1,e+n+1,cmp);memset(st,-1,sizeof st);memset(f,0x3f,sizeof f);f[0][0]=f[0][1]=0;for(int i=1;i<=n;i++){for(int j=0;j<i;j++){if(e[j].h-e[i].h<=m)//條件1{if(e[j].l>=e[i].l&&e[j].l<=e[i].r)//條件2{if(st[j][0]==-1)//條件3{f[i][0]=min(f[i][0],f[j][0]+e[j].h-e[i].h+e[j].l-e[i].l);f[i][1]=min(f[i][1],f[j][0]+e[j].h-e[i].h+e[i].r-e[j].l);st[j][0]=i;}}if(e[j].r>=e[i].l&&e[j].r<=e[i].r)//條件2{if(st[j][1]==-1)//條件3{f[i][0]=min(f[i][0],f[j][1]+e[j].h-e[i].h+e[j].r-e[i].l);f[i][1]=min(f[i][1],f[j][1]+e[j].h-e[i].h+e[i].r-e[j].r);st[j][1]=i;}}}}}ll ans=0x3f3f3f3f3f3f3f3f;for(int i=0;i<=n;i++)if(e[i].h<=m){if(st[i][0]==-1) ans=min(ans,f[i][0]+e[i].h);if(st[i][1]==-1) ans=min(ans,f[i][1]+e[i].h);}cout<<ans<<endl;}}

這是我一開始寫的wa代碼

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define debug(a,b) printf("%s = %d\n",a,b); typedef long long ll; using namespace std;inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=2000; struct node{int x1,x2,h; }a[maxn]; bool cmp(node a,node b){return a.h>b.h; } int dp[maxn][3]; int main() {int t;cin>>t;while(t--){memset(a,0,sizeof(a));int n=read(),x=read(),y=read(),MAX=read();for(int i=1;i<=n;i++){a[i].x1=read();a[i].x2=read();a[i].h=read();}a[0].x1=a[0].x2=x;a[0].h=y;sort(a+1,a+1+n,cmp);//從小到大 memset(dp,0x3f3f3f3f,sizeof(dp)); /*dp[i][0]表示到左側的距離 dp[i][1]表示到右側的距離 */dp[0][0]=0;dp[0][1]=0; for(int i=1;i<=n;i++){int l=a[i].x1,r=a[i].x2;for(int j=i-1;j>=0;j--){if(a[j].x2<=r&&a[j].x2>=l&&(a[j].h-a[i].h)<=MAX)//從第j個磚的右側下來{l=a[j].x2;dp[i][0]=min(dp[i][0],dp[j][1]+(a[j].h-a[i].h)+(a[j].x2-a[i].x1)); dp[i][1]=min(dp[i][1],dp[j][1]+(a[j].h-a[i].h)+(a[i].x2-a[j].x2)); }if(a[j].x1>=l&&a[j].x1<=r&&(a[j].h-a[i].h)<=MAX)//從第i個磚的左測下來{r=a[j].x1;dp[i][0]=min(dp[i][0],dp[j][0]+(a[j].h-a[i].h)+(a[j].x1-a[i].x1));dp[i][1]=min(dp[i][1],dp[j][0]+(a[j].h-a[i].h)+(a[i].x2-a[j].x1));}}}int l=-0x3f,r=0x3f;for(int j=n;j>=0;j--){if(a[j].x2<=r&&a[j].x2>=l&&(a[j].h)<=MAX){l=a[j].x2;dp[n+1][0]=min(dp[n+1][0],dp[j][1]+a[j].h);dp[n+1][1]=min(dp[n+1][1],dp[j][1]+a[j].h);}if(a[j].x1>=l&&a[j].x1<=r&&(a[j].h)<=MAX){r=a[j].x1;dp[n+1][0]=min(dp[n+1][0],dp[j][0]+a[j].h);dp[n+1][1]=min(dp[n+1][1],dp[j][0]+a[j].h);}} cout<<min(dp[n+1][0],dp[n+1][1])<<endl;} } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Help Jimmy POJ - 1661的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。