- This article is the basic of DP (Dynamic Programming) It is assumed that two Kaeru-kun problems can be solved.
It melts in DP! !! !! There was a problem that impressed me, so I will write it as an article. I know the idea of DP, but it doesn't connect with the actual problem! May be helpful (maybe not w)
Difficulty:205 After reading the problem, a full bit search and a 6-fold for statement crossed my head for a moment, but it seems to be useless.
By the way, you can solve it even if you can't think of DP. (I will post it as a separate solution at the end of the article.) But if you can't think of a DP I think it will take about 15 minutes to find the law.
** Fast solution is essential to raise the rate! ** **
The good thing about DP is (not limited to DP) The moment I realized that "this problem can be solved with DP!" ** I can code with almost brain death ** thing! Then ** I don't put my thoughts in there **, so I think that this level of problem will be able to aim for AC in about 5 minutes!
** The point is whether you realize that you can use DP! ** **
Anyway, prepare a notebook and a pen, Let's think about OK pattern and NG pattern.
1~99:NG 100,101,102,103,104,105:OK 106~199:NG 200,201,202,203,204,205,206,207,208,209,210:OK 211~299:NG 300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315:OK ...
Why is 200 ~ 205
OK?
That's because 100 ~ 105
is added to 100
which is OK originally.
Why is 201 ~ 206
OK?
That's because 100 ~ 105
is added to 101
which is OK originally.
I see!
Then, if you add 100 ~ 105
to each of the originally OK 200 ~ 210
, it seems to be OK.
Oh, I think I can go with DP!
If you accept 0 yen as OK, add 100 ~ 105
to 0
, which is originally OK, and it will be OK!
It looks like it will work!
All you have to do is code! !! !!
If you think about the Index number of DPMap for a moment, you should be able to die of brain death! Also, if you know that it's DP the moment you read the problem, you won't need a notebook and pen!
test.py
def I(): return int(input())
X = I()
dp = [0]*(X+1) #0_indexed
dp[0] = 1 #I'll accept 0 yen as OK!
for i in range(X+1):
if dp[i]:
for j in range(100,106):
if i+j<=X: #Measures for "out of lange".
dp[i+j] = 1
print(dp[-1])
When the next concrete example can be derived from the previous value when giving concrete examples in order → It seems worth considering whether DP can be used! !! !!
I didn't notice DP at first glance, so I did it here. The amount of code is small, but I think it will take some time to derive this code. (I wonder if this is faster for those who are accustomed to finding such a law)
test.py
def I(): return int(input())
X = I()
a,b = divmod(X,100)
print(1 if a*5>=b else 0)
end!
Recommended Posts