fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int rows;
  4. typedef long long ll;
  5. ll dp[5][100005];
  6. ll cost[5][100005];
  7. ll func(int i,int j)
  8. {
  9. if(i<1 || i>rows || j<1 || j>3)
  10. return 100000000;
  11. if(i==rows && j==2)
  12. return cost[i][j];
  13. if(i==rows && j==3)
  14. return 100000000;
  15. if(i==rows && j==1)
  16. return cost[i][j]+cost[i][j+1];
  17. if(dp[i][j]!=0)
  18. return dp[i][j];
  19. ll answer=100000000;
  20. if(j==1)
  21. {
  22. answer=min(answer,func(i,j+1));
  23. answer=min(answer,func(i+1,j));
  24. answer=min(answer,func(i+1,j+1));
  25. return dp[i][j]=cost[i][j]+answer;
  26. }
  27. if(j==2)
  28. {
  29. answer=min(answer,func(i,j+1));
  30. answer=min(answer,func(i+1,j));
  31. answer=min(answer,func(i+1,j+1));
  32. answer=min(answer,func(i+1,j-1));
  33. return dp[i][j]=cost[i][j]+answer;
  34. }
  35. if(j==3)
  36. {
  37. answer=min(answer,func(i+1,j));
  38. answer=min(answer,func(i+1,j-1));
  39. return dp[i][j]=cost[i][j]+answer;
  40. }
  41. }
  42. int main()
  43. {
  44. for(int i=1;;i++)
  45. {
  46. cin >> rows;
  47. if(rows==0)
  48. break;
  49. memset(dp,0,sizeof(dp));
  50. memset(cost,100000000,sizeof(cost));
  51. for(int i=1;i<=rows;i++)
  52. {
  53. for(int j=1;j<=3;j++)
  54. {
  55. cin >> cost[i][j];
  56. }
  57. }
  58. ll answer=func(1,2);
  59. cout << i << ". ";
  60. cout << answer << endl;
  61. }
  62. }
  63.  
Success #stdin #stdout 0s 11288KB
stdin
4
13 7 5
7 13 6
14 3 12
15 6 16
0
stdout
1. 22