fork(3) download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. using namespace std;
  5. const int INF = 987654321;
  6. int n,w;
  7.  
  8. int cost[10005][2];
  9. int cache[10005][2];
  10.  
  11. int get_dp(int idx, int type)
  12. {
  13.         if (idx >=n) return 0;
  14.  
  15.         int& ret = cache[idx][type];
  16.         if(ret != -1) return ret;
  17.         if (idx == n-1 && type == 0) {
  18.                 if(cost[n-1][0] + cost[n-1][1] <= w){
  19.                         return 1;
  20.                 }
  21.                 return 2;
  22.         }
  23.         if (idx == n-1 && type == 1) 
  24.                 return 1;
  25.  
  26.         ret = INF;
  27.         if(type == 0){
  28.                 if(cost[idx][0] + cost[idx][1] <= w){
  29.                         ret = min(ret, 1 + get_dp(idx+1, 0));
  30.                 }
  31.                 if(cost[idx][0] + cost[idx+1][0] <= w){
  32.                         if(cost[idx][1] + cost[idx+1][1] <= w){
  33.                                 ret = min(ret, 2 + get_dp(idx+2,0));
  34.                         }
  35.                         ret = min(ret, 2 + get_dp(idx+1,1));
  36.                 }
  37.                 ret = min(ret, 1 + get_dp(idx,1));
  38.  
  39.         }else if(type == 1){
  40.                 if(cost[idx][1] + cost[idx+1][1] <= w){
  41.                         if(cost[idx+1][0] + cost[idx+2][0] <= w){
  42.                                 ret = min(ret, 2 + get_dp(idx+2,1));
  43.                         }
  44.                         ret = min(ret, 2 + get_dp(idx+2,0));
  45.                 }
  46.                 ret = min(ret, 1 + get_dp(idx+1,0));
  47.         }
  48.         return ret;
  49. }
  50. int main()
  51. {
  52.         int t;
  53.         for(scanf("%d",&t);t;--t){
  54.                 memset(cache,-1,sizeof(cache));
  55.                 memset(cost,0,sizeof(cost));
  56.                 int ans = INF;
  57.                 scanf("%d%d",&n,&w);
  58.                 for(int j=0;j<2;++j){
  59.                         for(int i=0;i<n;++i){
  60.                                 scanf("%d",&cost[i][j]);
  61.                         }
  62.                 }
  63.                 ans = min(ans, get_dp(0,0));
  64.  
  65.                 int c00 = cost[0][0];
  66.                 int cn0 = cost[n-1][0];
  67.                 int c01 = cost[0][1];
  68.                 int cn1 = cost[n-1][1];
  69.                 if(n==1){
  70.                         printf("%d\n",ans);
  71.                         continue;
  72.                 }
  73.                 memset(cache,-1,sizeof(cache));
  74.                 if (c00 + cn0 <= w && c01 + cn1 <= w) {
  75.                         cost[0][0] = cost[n-1][0] = cost[0][1] = cost[n-1][1] = INF;
  76.                         ans = min(ans, get_dp(0,0) - 2);
  77.                         cost[0][0] = c00;
  78.                         cost[n-1][0] = cn0;
  79.                         cost[0][1] = c01;
  80.                         cost[n-1][1] = cn1;
  81.                 }
  82.  
  83.                 memset(cache, -1, sizeof(cache));
  84.                 if (c00 + cn0 <= w) {
  85.                         cost[0][0] = cost[n-1][0] = INF;
  86.                         ans = min(ans, get_dp(0,0) - 1);
  87.                         cost[0][0] = c00;
  88.                         cost[n-1][0] = cn0;
  89.                 }
  90.  
  91.                 memset(cache, -1, sizeof(cache));
  92.                 if (c01 + cn1 <= w) {
  93.                         cost[0][1] = cost[n-1][1] = INF;
  94.                         ans = min(ans, get_dp(0,0) - 1);
  95.                         cost[0][1] = c01;
  96.                         cost[n-1][1] = cn1;
  97.                 }
  98.                 printf("%d\n",ans);
  99.         }
  100. }
  101.  
Success #stdin #stdout 0s 3616KB
comments (?)
stdin
copy 
1
8 100
70 60 55 43 57 60 44 50
58 40 47 90 45 52 80 40
stdout
copy 
11
https://ideone.com/XPpr2X
BOJ 1006
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!