HDU ACM 1494 跑跑卡丁車動態(tài)規(guī)劃
來源：程序員人生 發(fā)布時間：2015-06-29 08:59:27 閱讀次數(shù)：4036次
分析：L段，N圈，則總共可表示為L*N段，用增加20%的能量表示1個狀態(tài)，則可表示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;
}
生活不易，碼農辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
