每日一dp(2)——龟兔赛跑（hdu 2059）

比较经典的动态规划的题目了

一般动态规划的想法都是先判断是否有最优子结构,无后效性。接着从状态转移入手,尽量细分状态(即给定N得到N+1),完了再递推计算

难点：转移方程，其一般也难在如何描述一个结点

有时候不太好做就结合使用记忆化搜索（从大到小搜索，因为多个小的可能会组成一个大的导致无效计算过多）

/************************************************************************/
/* 
动态规划三要素:
1.最优子结构 一个最优化策略的子策略总是最优的
2.无后效性   它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态
3.子问题重叠 动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法

很明显的状态转移
拆分的要素是时间,这里对于每个电桩都是一个状态断点,这里添加上起点终点构成0.1.2...N+1种状态
对于某一个电桩,其最优化策略是 min(之前各个电桩最优状态下加上充电时间)
dp[i]=min(dp[j])+T;0<=j<i<=N+1

*/
/************************************************************************/

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#define maxn 100+10

int L,C,T,N,VR,V1,V2,M,num;
float dp[maxn];
int charge[maxn];
int main()
{
    int i,j,k;
	float tmp,rabbit,TV1,ans;
    while(scanf("%d%d%d%d%d%d%d",&L,&N,&C,&T,&VR,&V1,&V2)!=EOF)
    {
		for(i=1;i<=N;i++)
			scanf("%d",charge+i);
		dp[0]=-1*T;//刚开始不用充电
		charge[0]=0;//补充充电桩
		charge[N+1]=L;//补充充电桩
		TV1=C/(V1+0.0);//计算骑在最大可行距离C下,电动车用时
		rabbit=L/(VR+0.0);//计算兔子用时
		for(i=1;i<=N+1;i++)
		{
			ans=1e9;//求dp[i]最小值
			for(j=0;j<i;j++)
			{
				tmp=dp[j];
				k=charge[i]-charge[j];
				if(C<k)//判断可否一次性用电动车骑完
					tmp+=TV1+(k-C+0.0)/V2;
				else
					tmp+=k/(V1+0.0);
				ans=ans>tmp?tmp:ans;//求dp[i]最小值
			}
			dp[i]=ans+T;
			
		}
		if(dp[N+1]<rabbit)
			printf("What a pity rabbit!\n");
		else
			printf("Good job,rabbit!\n");
		
	}
    return 0;
}

每日一dp(2)——龟兔赛跑（hdu 2059）,布布扣,bubuko.com

每日一dp(2)——龟兔赛跑（hdu 2059）

原文：http://blog.csdn.net/gg_gogoing/article/details/38509823