fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. char track[1005];
  5. int dp[1005][1000];
  6. int memo[1005]; //for bullets track
  7. int minDistance(int i,int bullets)
  8. {
  9.    if(track[i]=='S'&&bullets>=0)
  10.    return 0;
  11.  
  12.    if(bullets<0||i<0)
  13.    return 10000;
  14.  
  15.    if(memo[i]!=1000)
  16.    {
  17.     if(dp[i][memo[i]]!=10000&&bullets>=memo[i])
  18.     return dp[i][memo[i]];
  19.    }
  20.  
  21.  
  22.    if(track[i]=='#')
  23.    return minDistance(i-1,bullets-1) + 1;
  24.  
  25.    for(int k=0;k<i;k++)
  26.    {
  27.     dp[i][bullets] = min(dp[i][bullets],minDistance(k,bullets)+(i-k)*2+4);
  28.    }
  29.    /* for(int k=i-1;k>=0;k--)
  30.    {
  31.        dp[i][bullets] = min(dp[i][bullets],minDistance(k,bullets)+(i-k)*2+4);
  32.    }*/
  33.    dp[i][bullets] = min(dp[i][bullets],minDistance(i-1,bullets)+1);
  34.  
  35.    if(dp[i][memo[i]]>dp[i][bullets])
  36.    memo[i] = min(memo[i],bullets);
  37.  
  38.    return dp[i][bullets];
  39. }
  40. int main()
  41. {
  42.     int t,n,bullets;
  43.     scanf("%d",&t);
  44.     while(t--)
  45.     {
  46.  
  47.         scanf("%d%d%s",&n,&bullets,&track);
  48.  
  49.         for(int i=0;i<=n;i++)
  50.         for(int j=0;j<=bullets;j++)
  51.         dp[i][j] = 10000;
  52.  
  53.         for(int i=0;i<=n;i++)
  54.         memo[i]=10000;
  55.  
  56.         printf("%d\n",minDistance(n-1,bullets));
  57.     }
  58.     return 0;
  59. }
  60.  
Success #stdin #stdout 0s 7228KB
comments (?)
stdin
copy 
10
7 3
S00000E
2 2
SE
4 1
S00E
8 1
S0000##E
8 3
S0#00#0E
7 2
S0#0##E
10 4
S00#0#0##E
5 2
S000E
7 1
S0##00E
9 0
S0000##0E
stdout
copy 
6
1
3
13
7
12
9
4
12
15
https://ideone.com/Daq0x6
language:
C++ (gcc 8.3)
created:
9 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!