HDU ACM 1494 跑跑卡丁车动态规划
来源：程序员人生 发布时间：2015-06-29 08:59:27 阅读次数：3882次
分析：L段，N圈，则总共可表示为L*N段，用增加20%的能量表示1个状态，则可表示20%,40%,%60。。。，共15个，注意第15个时要清零到两个能量卡；用dp[i][j]表示在第i段能量为j的已用时的最少时间。则可得到方程1、不用能量卡时dp[i][j]=min(dp[i][j]，dp[i⑴][j⑴]+a[i⑴]；用能量卡时dp[i][j⑸]=min(dp[i][j⑸],dp[i⑴][j]+b[i⑴])。
#include<iostream>
using namespace std;
int Ai[102];
int Bi[102];
int dp[10010][16];
#define MAX 1000000
int main()
{
int L,N;
int i,j,len,res;
while(scanf("%d %d",&L,&N)==2)
{
len=L*N;
for(i=0;i<L;i++) scanf("%d",&Ai[i]);
for(i=0;i<L;i++) scanf("%d",&Bi[i]);
for(i=0;i<=len;i++)
for(j=0;j<=15;j++)
dp[i][j]=MAX;
dp[0][0]=0;
for(i=1;i<=len;i++)
{
for(j=15;j>=1;j--)
dp[i][j]=dp[i][j]<dp[i⑴][j⑴]+Ai[(i⑴)%L]?dp[i][j]:dp[i⑴][j⑴]+Ai[(i⑴)%L];//不使用加速卡
for(j=14;j>=5;j--)
dp[i][j⑸]=dp[i][j⑸]<dp[i⑴][j]+Bi[(i⑴)%L]?dp[i][j⑸]:dp[i⑴][j]+Bi[(i⑴)%L];//使用加速卡
dp[i][10]=dp[i][10]<dp[i][15]?dp[i][10]:dp[i][15]; //15时能量减为2个加速卡的能量.
}
for(res=MAX,i=0;i<=15;i++)
res=res<dp[len][i]?res:dp[len][i];
printf("%d
",res);
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
