注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1494  

2012-10-17 22:40:00|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

中文题,题意明确了~
这题很难想到用动态规划做,后来看了网上的做法,需要做一个巧妙的转换:把能量槽的15种状态用一个变量从0到14来表示,从0开始,20%,40%等等
然后就可以用一个二维数组动规求解了
需注意的地方:如何集气到2个加速卡+100%,也就是300%的能量的时候,需要减掉一个加速卡,因为最多只有两个加速卡
/*
 * fudq.cpp
 *
 *  Created on: 2012-10-17
 *  f[i][j]表示行驶了i段路程,j的状态下最小花费
 *  如果是普通模式,f[i+1][temp+1]=Min(f[i+1][temp+1],f[i][j]+a[i%L]);
 *  如果是加速模式,f[i+1][j-5]=Min(f[i+1][j-5],f[i][j]+b[i%L]);
 */
#include<algorithm>
#include<stdio.h>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<map>
#include<iostream>
using namespace std;
#define NUM 999999
int f[10010][16];

int Min(int a,int b)
{
return a<b?a:b;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("testin.txt","r",stdin);
#endif
    int i,j,L,N,res,temp,a[102],b[102];
    while(scanf("%d%d",&L,&N)!=EOF)
    {
    for(i=0;i<L;i++)
    scanf("%d",&a[i]);
    for(i=0;i<L;i++)
    scanf("%d",&b[i]);

    //初始化
    for(i=0;i<=L*N;i++)
    for(j=0;j<15;j++)
    f[i][j]=NUM;
    f[1][1]=a[0];

    //状态转移
    for(i=1;i<L*N;i++)
    for(j=0;j<15;j++)
    {
    temp=j;
    if(j==14)
    temp=9;
    f[i+1][temp+1]=Min(f[i+1][temp+1],f[i][j]+a[i%L]);

    if(j>=5)
    f[i+1][j-5]=Min(f[i+1][j-5],f[i][j]+b[i%L]);
    }

    //找最小值
    res=NUM;
    for(i=0;i<15;i++)
    if(f[L*N][i]<res)
    res=f[L*N][i];
    printf("%d\n",res);
    }
    return 0;
}
  评论这张
 
阅读(83)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018