×

# Help in C. Three Displays

 0 Hello, I was solving this problem and firstly I formulated recursion which shows TLE on test 11(it obviously should). I then tried saving the answer, approaching the problem like dp. But I don't know why the code shows WA on test 7. I think I doing some mistake while saving the answer. Any help would be highly appreciated. Thanks :) asked 30 May '18, 09:07 614●1●9 accept rate: 12%

 1 vector fs(n); vector c(n); vector > dp(n, vector(3,INT_MAX)); for(int i=0;i>fs[i]; } for(int i=0;i>c[i]; dp[i][0]=c[i]; } for(int i=1;ifs[j]){ dp[i][1] = min(dp[i][1], dp[j][0]+c[i] ); } } } for(int i=1;i fs[j] && dp[j][1]!=INT_MAX){ dp[i][2] = min( dp[i][2], dp[j][1]+c[i]); } } } int ans= dp[0][2]; for(int i=1;i
 1 Hey! Dishant in your dp you need to make cache[pos][last][second_last] as it might come to pos last with second last chosen or different from before or even not chosen So although answer will be different your code will return the same value. But if you make the dp as I told it would give tle (as it would be O(n^3)) so you should do something like meet2mky said Here is my code - http://codeforces.com/contest/987/submission/38740788 EDIT : Example test case consider the input 7 1 2 3 4 5 6 7 7 6 5 4 3 2 1 your code is giving output 10 (due to multiple same pos last occurance) but the ans is 6 the cost of last 3 boards 1+2+3=6 Sorry for bad english answered 30 May '18, 17:48 3★ssp547 307●7 accept rate: 25% Thanks for the help :) (30 May '18, 21:16)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,172
×682

question asked: 30 May '18, 09:07

question was seen: 205 times

last updated: 30 May '18, 21:17