pku1036Gangsters 强盗进旅馆（动态规划）

-

第一种解法：

dp[i][j]表示在i时间j状态下的最优解，递推公式如下：

dp[0][0]=0

dp[0][s]=-inf  1=<s<=k

dp[t][s]=max(dp[t-1][s-1],dp[t-1][s],dp[t-1][s+1])+{g.p}(g.t=t&&g.s=s)   1=<t<=T         0=<s<=k

结果：内存超出。。。。。。。。。

代码如下：

Code

解法二：

首先对强盗排序（按时间），对每

个强盗编号，算最优值

公式如下：

dp[i]=-1表示第i个编号的强盗不能进旅馆

否则表示而且到这个强盗到来的时间时已经求得的最优值

dp[i]=max(dp[j]+g[i].p) (0<=j<i<=n且g[i].t-g[j].t>=|g[i].s-g[j].s|)

代码如下：

 

Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/pandy/p/1341757.html