HDu 1494カートを走る

http://acm.hdu.edu.cn/showproblem.php?pid=1494
dp[i][j]はi段目の道路であり、j個のエネルギーが蓄積されている.

 1 #include <cstdio>

 2 #include <cstring>

 3 #include <algorithm>

 4 #define ll int

 5 using namespace std;

 6 const int inf=1<<30;

 7 

 8 ll a[20000],b[20000];

 9 ll dp[10010][20];

10 int l,n;

11 

12 int main()

13 {

14     while(scanf("%d%d",&l,&n)!=EOF)

15     {

16         for(int i=1; i<=l; i++)

17         {

18             scanf("%d",&a[i]);

19         }

20         for(int i=1; i<=l; i++)

21         {

22             scanf("%d",&b[i]);

23         }

24         for(int i=l+1; i<=n*l; i++)

25         {

26             a[i]=a[i-l];

27             b[i]=b[i-l];

28         }

29         for(int i=1; i<15; i++)

30         {

31             dp[0][i]=inf;

32         }

33         dp[0][0]=0;

34         for(int i=1; i<=n*l; i++)

35         {

36             for(int j=0; j<15; j++)

37             {

38                 if(j==0) dp[i][j]=dp[i-1][5]+b[i];

39                 else

40                 {

41                     dp[i][j]=dp[i-1][j-1]+a[i];

42                     if(j==10)

43                         dp[i][j]=min(dp[i][j],dp[i-1][14]+a[i]);

44                     if(j+5<15)

45                         dp[i][j]=min(dp[i][j],dp[i-1][j+5]+b[i]);

46                 }

47             }

48         }

49         ll ans=dp[l*n][0];

50         for(int i=1; i<15; i++)

51         {

52             ans=min(ans,dp[n*l][i]);

53         }

54         printf("%d
",ans);

55     }

56     return 0;

57 }

View Code