This is a review article for DP100 Question Bacha.
(I was thinking of solving 100 questions, but I'm tired of it, so I think this article will stop updating.)
I will try to summarize the DP method as systematically as possible.
** DP is enabled if there are continuous constraints **. In addition, this time we can see that it seems possible to ** limit the state with 3 types of pasta **.
Since we need information on which pasta was eaten on the ** $ i $ day and how many days in a row **, set the DP as follows (if it is decided continuously).
$ dp [i] [j] [k]: = $ (Number of combinations of pasta $ j $ eaten by $ i $ day (1-indexed) in a row)
The ** transition ** looks like this: Also, here, consider the transition assuming that you ate pasta $ k $ **, ** $ i + 1 $ day pasta $ j $ ** on the ** $ i $ day.
(1) When $ k = j $
(2) When $ k! = J $
(✳︎) $ i + 1 $ If the pasta on the day is decided, only $ j = pasta [i + 1] $ is considered, and if it is not decided, any $ j $ is considered.
A total of about $ n \ times 3 \ times 3 $ times should be calculated, and the maximum is about $ 1000 $ times.
mod=10000
n,k=map(int,input().split())
pasta=[-1]*n
for i in range(k):
a,b=map(int,input().split())
pasta[a-1]=b-1
dp=[[[0]*2 for i in range(3)] for j in range(n)]
if pasta[0]==-1:
for i in range(3):
dp[0][i][0]=1
else:
dp[0][pasta[0]][0]=1
#Where are you looking now
for i in range(n-1):
if pasta[i+1]!=-1:
#Where is it changing now(pasta[i]only)
for j in range(3):
if j==pasta[i+1]:
#If you choose itself
dp[i+1][j][1]+=dp[i][j][0]
#When going to a different place
for k in range(3):
if k!=j:
dp[i+1][j][0]+=sum(dp[i][k])
else:
for j in range(3):
#If you choose itself
dp[i+1][j][1]+=dp[i][j][0]
#When going to a different place
for k in range(3):
if k!=j:
dp[i+1][j][0]+=sum(dp[i][k])
ans=0
for i in range(3):
ans+=sum(dp[n-1][i])
print(ans%mod)
Since it is recursive, it can be solved by ** memoization recursive procedure ** and can be reduced to DP.
** The number will always increase by adding the sum of digits **. Therefore, count the number of cases in the manner of memoization recursion. That is, the DP is set as follows.
$ dp [i]: = $ (number when it becomes $ i $ in the sum of digits operation)
If the function that calculates the sum of digits of $ n $ is $ check (n) $ (the amount of calculation is $ O (\ log {n}) $), the transition will be as follows.
The amount of calculation is $ O (n \ log {n}) $, so it is enough.
def check(n):
ret=0
while n!=0:
ret+=(n%10)
n//=10
return ret
n=int(input())
dp=[1]*n
for i in range(n):
c=check(i+1)
if i+c<n:
dp[i+c]+=dp[i]
print(dp[n-1])
** Subtraction of numbers can be considered a transition **. Also, ** it is difficult to greedily decide the order **.
Since it is sufficient to save the minimum number of times for each number, set the following DP.
$ dp [i]: = $ (minimum number of attempts when reduced to $ i $)
In addition, the transition is easy and is as follows. At this time, the number to be reduced is $ j = 1 $ ~ $ 3 $.
It should be noted here that it is necessary to confirm that it is $ i-j \ geqq 0 $ (** out-of-range reference **) and that $ i-j $ is not NG.
n=int(input())
ng={int(input()) for i in range(3)}
if n in ng:
print("NO")
exit()
#The number of times
inf=100000000000
dp=[inf]*(n+1)
dp[n]=0
#0,1 mistaken grass
for i in range(n,0,-1):
if dp[i]!=inf:
for j in range(max(i-3,0),i):
if j not in ng:
dp[j]=min(dp[j],dp[i]+1)
print("YES" if dp[0]<=100 else "NO")
4,D - Prediction and Restriction
There are ** and $ 3 ^ n $ ways to think honestly about the number of cases **, but it can be summarized well by using ** DP ** that limits the state. In addition, the condition ** $ K $ different from the previous move ** can be seen as a transition.
($ t [i]: = $ (hand of opponent on $ i $ day), $ janken [i]: = $ (score obtained by buying with hand $ i $))
You need information on which move to take at the $ i $ time, and the DP can be as follows.
$ dp [i] [j]: = $ (maximum score when you move $ j $ for the $ i $ time)
Also, the transition is as follows (** I was thinking about the transition properly **, so I got stuck in the implementation here). Furthermore, Goo is 0, Choki is 1, and Par is 0. Also note that ** initialization ** is done at $ i = $ 0 ~ $ k-1 $.
If the $ i-k $ first move is $ l $, $ i $ the second move is $ j $, then ** $ l! = J $
(1) If you win the $ i $ time ... $ (j + 1) % 3 = t [i] $
(2) If you lose or draw for the $ i $ time
Also, the maximum score you are looking for is ** $ mod \ k $ total , so the final answer is $ max (dp [$ nk
n,k=map(int,input().split())
dp=[[0,0,0] for i in range(n)]
janken=list(map(int,input().split()))
t=[0 if i=="r" else 1 if i=="s" else 2 for i in input()]
#Decide by looking at the hand immediately after
for i in range(n):
if i<k:
for j in range(3):
if (j+1)%3==t[i]:
dp[i][j]=janken[j]
else:
#update
for j in range(3):
#Source of transition
for l in range(3):
if j!=l:
if (j+1)%3==t[i]:
dp[i][j]=max(dp[i][j],janken[j]+dp[i-k][l])
else:
dp[i][j]=max(dp[i][j],dp[i-k][l])
ans=0
for i in range(n-k,n):
ans+=max(dp[i])
print(ans)
** It is best if you can think in order from the previous day **, and ** the greedy algorithm seems to be difficult ** (actually it is not so difficult).
(In the following, the operation of buying all stocks or selling all stocks is optimal, but I will not prove it here.)
If you normally think about the maximum amount of money you have on the $ i $ day, it becomes very difficult to classify whether you have shares or not. Therefore, considering that ** eventually sell all stocks **, the following DP can be set.
$ dp [i]: = $ (Maximum amount of money you have when selling all stocks on the $ i $ day)
At this time, if you pay attention to when you buy all the stocks, you can express the transition as follows as ** buying all the stocks on the $ j $ day **.
dp[i]=max(dp[i],(dp[j]//a[j])*a[i]+dp[j]%a[j])
In addition, the amount of calculation is $ O (N ^ 2) $, which is sufficient. At first I was trying to solve it with $ O (N) $, but it is clear from the constraints that $ O (N ^ 2) $ is enough.
n=int(input())
a=list(map(int,input().split()))
dp=[0]*n
dp[0]=1000
for i in range(1,n):
dp[i]=dp[i-1]
for j in range(i):
dp[i]=max(dp[i],(dp[j]//a[j])*a[i]+dp[j]%a[j])
print(dp[n-1])
I'd like to think of a magical combination, but ** it seems difficult to greedily choose **. ** If you manage the necessary magical power for each physical strength ** It looks good and you think of DP.
It is good to set up the following DP.
$ dp [i]: = $ (Minimum required magic power when the monster's remaining health is $ i $)
At this time, the transition is simple, and if the power of a certain magic is $ a $ and the power of magic is $ b $, it will be as follows.
Also, ** magic can be used any number of times **, so you can calculate DP in the direction of $ h \ rightarrow0 $.
h,n=map(int,input().split())
inf=100000000000
dp=[inf]*(h+1)
dp[h]=0
for i in range(n):
a,b=map(int,input().split())
for j in range(h,-1,-1):
dp[max(j-a,0)]=min(dp[max(j-a,0)],dp[j]+b)
print(dp[0])
The operation can be ** paraphrased ** by multiplying $ A \ _i, A \ _j $ by -1, so it can be easily solved by classifying the cases with even or odd negative numbers. I will.
However, even such problems can be pushed by DP. This is because it is useless to perform each operation with $ i $ more than once, so it is only necessary to perform the operation once, and at this time ** the operations can be performed monotonously from the front **.
The following DP should be set. (Although $ i $ and $ i + 1 $ are selected in the operation in the problem statement, the operation to select $ i-1 $ and $ i $ is the $ i $ th operation for the convenience of implementation. I will.)
$ dp [i] [j]: = $ (Maximum total value of the sequence when the operation up to the $ i $ th operation is performed and the $ i $ th operation is performed (or not))
However, it is assumed that $ j = 0 $ is not performed and $ j = 1 $ is performed.
In addition, the transition at this time is as follows.
(1) When operating at the $ i $ th
It should be noted that ** $ i-1 $ whether or not the operation was performed ** at that time is $ a [i-1] $ or $ -a [i-1] $ changes. ** Pay attention to the difference **.
(2) When no operation is performed at the $ i $ th
n=int(input())
a=list(map(int,input().split()))
dp=[[0,0] for i in range(n)]
dp[0][0]=a[0]
dp[1][0]=dp[0][0]+a[1]
dp[1][1]=dp[0][0]-2*a[0]-a[1]
for i in range(2,n):
dp[i][0]=max(dp[i-1])+a[i]
dp[i][1]=max(dp[i-1][0]-2*a[i-1]-a[i],dp[i-1][1]+2*a[i-1]-a[i])
print(max(dp[n-1]))
It can be split if only the neighbors are different, and the substring should be as short as possible to split more. At this time, even if the subsequence with a length of 3 or more is divided, the condition of the subject can be satisfied, so it should be ** a character string with a length of 1 or 2 **. At this point, we will first consider using a greedy algorithm that makes the length of the subsequences one by one as much as possible, but you may not be confident that the implementation is a little cumbersome. In this case, DP can be used to ** AC ** in a clear and legitimate way.
Cut out a substring so that the length is 1 as much as possible from the previous character. The length is 2 only when the character of length 1 is cut out immediately before and equal to the next character. Implementation can be performed by recording the substring cut out immediately before.
s=input()
ans=1
l=len(s)
now=s[0]
i=1
while i<l:
if now!=s[i]:
now=s[i]
ans+=1
i+=1
else:
if len(now)==2:
now=s[i]
ans+=1
i+=1
else:
if i<l-1:
now=s[i:i+2]
i+=2
ans+=1
else:
break
#print(i)
print(ans)
You can ** limit the number of states **, noting that you can only cut out 1 or 2. Therefore, the DP can be set as follows.
$ dp [i] [j]: = $ (** Maximum number of divisions in the string whose $ i $ th is ** length $ j + 1 $)
Also, the transition is as follows, considering the transition toward $ dp [i] $. Here, let the $ i $ character be $ s [i] $.
(1) When the $ i $ th is included in a subsequence of length 1
When the $ i-1 $ th is included in a subsequence of length 2, it can be selected unconditionally, and $ dp [i] [0] = dp [i-1] [1] + 1 $. .. $ i-1 When the $ th is included in a subsequence of length 1, $ s [i-1]! = S [i] $ when $ dp [i] [0] = max (dp [i] [ It becomes 0], dp [i-1] [0] + 1) $.
(2) When the $ i $ th is included in a subsequence of length 2
When the $ i-2 $ th is included in a subsequence of length 1, it can be selected unconditionally, and $ dp [i] [1] = dp [i-2] [0] + 1
s=input()
n=len(s)
dp=[[0,0] for i in range(n)]
dp[0][0]=1
for i in range(1,n):
dp[i][0]=dp[i-1][1]+1
if s[i-1]!=s[i]:
dp[i][0]=max(dp[i][0],dp[i-1][0]+1)
if i>1:
dp[i][1]=dp[i-2][0]+1
if i>2:
if s[i-3:i-1]!=s[i-1:i+1]:
dp[i][1]=max(dp[i][1],dp[i-2][1]+1)
print(max(dp[n-1]))
First, there are $ _ {16} C_2 $ combinations of shortcuts. Consider the maximum number of button inputs required for each combination of shortcuts. At this time, ** it is difficult to think greedily **, and ** the operation of arranging characters in order can be regarded as a transition **, so you can think of DP.
It is assumed that the shortcut command is fixed at $ L, R $. At this time, set DP as follows.
$ dp [i]: = $ (minimum number of times when the command is decided up to $ i $)
The DP transition at this time is as follows. Here, I considered the DP to be passed from the $ k $ th.
(1) When not using shortcuts
(2) When using shortcuts
If the shortcut matches the $ k + 1 $ and $ k + 2 $ th characters ($ s [k + 1: k + 3] == l $ or $ s [k + 1: k + 3] = = r $),
command=[i+j for i in "ABXY" for j in "ABXY"]
#print(command)
n=int(input())
s=input()
inf=100000000000
ans=inf
for i in range(16):
l=command[i]
for j in range(16):
r=command[j]
dp=[inf]*n
dp[0]=1
if n>1:
if s[0:2]==l or s[0:2]==r:
dp[1]=1
for k in range(n):
if k+1<n:
dp[k+1]=min(dp[k+1],dp[k]+1)
if k+2<n:
if s[k+1:k+3]==l or s[k+1:k+3]==r:
dp[k+2]=min(dp[k+2],dp[k]+1)
#print(dp[n-1])
ans=min(ans,dp[n-1])
print(ans)
On the contrary, I think it is better not to select DP for this problem. In other words, you can take a ** extreme point **, which meets one of the following conditions:
In addition, you can do it greedily to meet this condition, and you can do it with the following policy.
If the last selected rating is $ x $ and the rating of the point you are looking at is $ r \ _i $, the conditions for selecting $ r \ _i $ are one of the following.
When either of these holds, it can be included in the graph of the subject, and you can greedily select the elements one by one.
Also, ** left and right ratings can be included because they always meet the conditions of the graph **. Therefore, if the number of points included in the graph that is greedily selected is less than 3, -1 should be output, and if it is 3 or more, the number of points should be output.
n=int(input())
r=list(map(int,input().split()))
if n<3:
print(0)
exit()
ans=[r[0]]
for i in range(1,n-1):
if ans[-1]<r[i] and r[i]>r[i+1]:
ans.append(r[i])
if ans[-1]>r[i] and r[i]<r[i+1]:
ans.append(r[i])
if i==n-2:
ans.append(r[i+1])
if len(ans)<3:
print(0)
else:
print(len(ans))
Recommended Posts