Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- int dp[25][10][10];
- int n;
- int m[25][3];
- int rec(int i, int prev_color, int first_color) {
- if(i == 0) {
- if(prev_color == first_color) {
- return m[0][prev_color];
- }
- return 100000;
- }
- if(dp[i][prev_color][first_color] != -1) {
- // return dp[i][prev_color][first_color];
- }
- int result = 100000;
- for(int j = 0; j < 3; j++) {
- if(prev_color != j) {
- result = min(result, rec(i - 1, j, first_color) + m[i][j]);
- }
- }
- dp[i][prev_color][first_color] = result;
- return result;
- }
- int main()
- {
- cin>>n;
- for(int i=0; i<n; i++){
- for(int j=0; j<3; j++){
- cin>>m[i][j];
- }
- }
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < 3; j++) {
- for(int k = 0; k < 3; k++) {
- dp[i][j][k] = -1;
- }
- }
- }
- int result = 2e9;
- for(int i = 0; i < 3; i++) {
- for(int j = 0; j < 3; j++) {
- if(i != j) {
- result = min(result, rec(n - 1, i, j));
- }
- }
- }
- cout << result<< endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement