I want to confirm the mistake in the code that I thought about "Atcodr Beginner Contest 015 D Takahashi-kun's suffering"
Test case 36/47 is correct and 11 questions are incorrect.Corresponding source code
What I tried
W = int (input ()) N, K = map (int, input (). split ()) ab = [list (map (int, input (). split ())) for _ in range (N)] dp = [ * (W + 1) for _ in range (N + 1)] cnt = [ * (W + 1) for _ in range (N + 1)] for i in range (N): a, b = ab [i] for j in range (W + 1): if j-a<0: dp [i + 1] [j] = dp [i] [j] cnt [i + 1] [j] = cnt [i] [j] else: else: if dp [i] [j]<dp [i] [j-a] + b: cnt [i + 1] [j] = cnt [i] [j-a] +1 dp [i + 1] [j] = dp [i] [j-a] + b else: else: cnt [i + 1] [j] = cnt [i] [j] dp [i + 1] [j] = dp [i] [j] ans = 0 for i in range (W + 1): if cnt [N] [i]<= K: ans = dp [N] [i] print (ans)
I've been learning dynamic programming recently, and I wondered if I could use the 2D DP table that often appears. Since there are many variables for constraints, I think that one 2D DP table is not enough, so I created a DP table with a variable name of cnt and counted the number of screenshots separately from the main DP table (variable name: dp). I wondered if it would work. The sample case passed without any problem, and the table seemed to be updated well, so I thought it would be a good idea, but it turned out to be test case WA. Is the idea wrong? Thank you.
Answer # 1
If the number of sheets exceeds K, it cannot be used no matter how important the total is
In the current code, if the width is the same and the importance is high, it is updated without looking at the number of sheets at all, but with that, there are combinations that can not be used beyond K, and there are many sheets and it is not possible to increase the importance later, so the future potential Combinations without are likely to remain in the table.
Here's an example that doesn't work. try it.
2 3 1 twenty three 1 2 1 2
- i have a question about basic python problems
- python - to make 6 question items in a set of 3 questions random
- python 3x - i have a question about sleep in python
- python 3x - "rgb triplets" atcoder abc162 inquiry about computational complexity
- python - [question] about combining pandas data frames
- python - atcoder bug not found [abc083b: some sums]
- python - regular expression wildcard? i have a question about
- python - tkinter photo image question
- i have a question about runtime errors and exception handling in python
- python 3x - i have a question about pipenv i want to set the directory location
- python 3x - "friends" atcoder abc177 code counterexample question (union find)
- python 3x - "colorful leaderboard" atcoder abc064 code counterexample
- python - you may need to restart the kernel to use updated packages error
- php - coincheck api authentication doesn't work
- php - i would like to introduce the coincheck api so that i can make payments with bitcoin on my ec site
- [php] i want to get account information using coincheck api
- the emulator process for avd pixel_2_api_29 was killed occurred when the android studio emulator was started, so i would like to
- python 3x - typeerror: 'method' object is not subscriptable
- i want to call a child component method from a parent in vuejs
- dart - flutter: the instance member'stars' can't be accessed in an initializer error
- xcode - pod install [!] no `podfile 'found in the project directory