有后效性的動(dòng)態(tài)規(guī)劃？（然而并不是）

GO：洛谷

---

?

題目描述

Sue和Sandy最近迷上了一個(gè)電腦游戲，這個(gè)游戲的故事發(fā)在美麗神秘并且充滿刺激的大海上，Sue有一支輕便小巧的小船。然而，Sue的目標(biāo)并不是當(dāng)一個(gè)海盜，而是要收集空中漂浮的彩蛋，Sue有一個(gè)秘密武器，只要她將小船劃到一個(gè)彩蛋的正下方，然后使用秘密武器便可以在瞬間收集到這個(gè)彩蛋。然而，彩蛋有一個(gè)魅力值，這個(gè)魅力值會(huì)隨著彩蛋在空中降落的時(shí)間而降低，Sue要想得到更多的分?jǐn)?shù)，必須盡量在魅力值高的時(shí)候收集這個(gè)彩蛋，而如果一個(gè)彩蛋掉入海中，它的魅力值將會(huì)變成一個(gè)負(fù)數(shù)，但這并不影響Sue的興趣，因?yàn)槊恳粋€(gè)彩蛋都是不同的，Sue希望收集到所有的彩蛋。

然而Sandy就沒(méi)有Sue那么浪漫了，Sandy希望得到盡可能多的分?jǐn)?shù)，為了解決這個(gè)問(wèn)題，他先將這個(gè)游戲抽象成了如下模型：

以Sue的初始位置所在水平面作為x軸。

一開(kāi)始空中有N個(gè)彩蛋，對(duì)于第i個(gè)彩蛋，他的初始位置用整數(shù)坐標(biāo)（xi, yi）表示，游戲開(kāi)始后，它勻速沿y軸負(fù)方向下落,速度為vi單位距離/單位時(shí)間。Sue的初始位置為(x0, 0)，Sue可以沿x軸的正方向或負(fù)方向移動(dòng)，Sue的移動(dòng)速度是1單位距離/單位時(shí)間，使用秘密武器得到一個(gè)彩蛋是瞬間的，得分為當(dāng)前彩蛋的y坐標(biāo)的千分之一。

現(xiàn)在，Sue和Sandy請(qǐng)你來(lái)幫忙，為了滿足Sue和Sandy各自的目標(biāo)，你決定在收集到所有彩蛋的基礎(chǔ)上，得到的分?jǐn)?shù)最高。

輸入格式

第一行為兩個(gè)整數(shù)N, x0用一個(gè)空格分隔，表示彩蛋個(gè)數(shù)與Sue的初始位置。

第二行為N個(gè)整數(shù)xi，每?jī)蓚€(gè)數(shù)用一個(gè)空格分隔，第i個(gè)數(shù)表示第i個(gè)彩蛋的初始橫坐標(biāo)。

第三行為N個(gè)整數(shù)yi，每?jī)蓚€(gè)數(shù)用一個(gè)空格分隔，第i個(gè)數(shù)表示第i個(gè)彩蛋的初始縱坐標(biāo)。

第四行為N個(gè)整數(shù)vi，每?jī)蓚€(gè)數(shù)用一個(gè)空格分隔，第i個(gè)數(shù)表示第i個(gè)彩蛋勻速沿y軸負(fù)方向下落的的速度。

輸出格式

一個(gè)實(shí)數(shù)，保留三位小數(shù)，為收集所有彩蛋的基礎(chǔ)上，可以得到最高的分?jǐn)?shù)。

---

　　這道題容易看出是動(dòng)態(tài)規(guī)劃，但是轉(zhuǎn)移方程不好設(shè)計(jì)：每走一步都會(huì)改變當(dāng)前所有未收集位置上的狀態(tài)，不好從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)，但是我們可以提前將它計(jì)算出來(lái)。

　　我們?cè)O(shè)f[k][i][j]表示[i,j]已經(jīng)走了，此時(shí)在k位置(k=0 left|k=1 right)時(shí)的最大分?jǐn)?shù)，每走到一個(gè)新的格子，先將價(jià)值減去其余格子下降的高度和，再加上當(dāng)前格的價(jià)值，以此方式考慮從左還是右轉(zhuǎn)移即可。

　　具體細(xì)節(jié)：

1.可以用前綴和處理每一個(gè)格子的價(jià)值，高度和即為d*{sum[1~i)+sum(j,n]},d為路程。

2.預(yù)處理就是將原點(diǎn)加入序列中，排序保證每次轉(zhuǎn)移都是向最近的格子(先取比迂回取更優(yōu))，再將初始狀態(tài)賦為0，其余為負(fù)無(wú)窮即可。

具體看程序：

#include<bits/stdc++.h> using namespace std; #define f(i,a,b) for(int i=a;i<=b;i++) const int N=1e3+10; struct ball{int x,y,v; }a[N]; bool cmp(ball t1,ball t2){return t1.x<t2.x;} int n,x0; int s[N],l[N][N],r[N][N]; int sum(int i,int j){return s[n]-s[j]+s[i-1]; } int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } int main(){n=read();x0=read();f(i,1,n){a[i].x=read();}f(i,1,n){a[i].y=read();}f(i,1,n){a[i].v=read();}a[++n].x=x0;sort(a+1,a+n+1,cmp);f(i,1,n){s[i]=s[i-1]+a[i].v;}memset(l,-0x3f,sizeof(l));memset(r,-0x3f,sizeof(r));f(i,1,n){if(a[i].v==0&&a[i].x==x0) l[i][i]=r[i][i]=0;}f(i,2,n){f(j,1,n-i+1){int k=j+i-1;l[j][k]=a[j].y+max(l[j+1][k]-(a[j+1].x-a[j].x)*sum(j+1,k),r[j+1][k]-(a[k].x-a[j].x)*sum(j+1,k));r[j][k]=a[k].y+max(r[j][k-1]-(a[k].x-a[k-1].x)*sum(j,k-1),l[j][k-1]-(a[k].x-a[j].x)*sum(j,k-1));}}printf("%.3lf",max(l[1][n],r[1][n])/1000.0);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Nelson992770019/p/11469636.html

總結(jié)

以上是生活随笔為你收集整理的【DP专题】——洛谷P2466 [SDOI2008]Sue的小球的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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