程序员人生 网站导航

HDU ACM 1494 跑跑卡丁车动态规划

栏目:综合技术时间:2015-06-29 08:59:27

分析: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; }


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐