AtCoder Regular Contest 059
The last two DPs in this issue are very fun.
The code is here.
C Be Together
The meaning of the question is to give n numbers and they must be unified into the same number. The cost is the square of the difference. Ask for the minimum cost.
Due to the small number and scope, direct violence.
D Unbalanced
The purpose of the question is to give a string, find out whether there is an unbalanced string in the substring of this string, and output its position. The so-called unbalanced string means that the number of characters in the string is greater than half the length of the string.
It is found that the smallest unbalanced string has more than two identical characters within three, and any unbalanced string must be based on this. So just be violent one character at a time.
E Children and Candies
The meaning of the question is that there are n children and c candies, and c candies are allocated to n children. Assume that the number of candies the child gets is a, the excitement value is xi, the child’s happiness value is xi^a, and the total activity value of the kindergarten is the product of the happiness values of all children.
Now the excitement value of each child ranges from Ai to Bi. Ask the sum of the kindergarten activity values (…….) in all situations.
dp[i][c] represents the total activity value of i children distributing c candies. Then analyze this function carefully. When it reaches i+1, the transfer situation is
$$
dp[i+1][c]=\sum_{j=0}^{c}dp[i][j]*(\sum_{x=A[i+1]}^{B[i+1]}x^{c-j})
$$
Therefore, preprocess the prefix sum of x and transfer it directly.
F Unhappy Hacking
The meaning of the question is that there are only three keys on this computer keyboard: 0, 1 and delete key. Now after pressing the keyboard n times, there is a string. How many key situations can form a changed string.
dp[n][c] represents the number of ways to form a string of length c after pressing the keyboard n times. For the n+1th time the keyboard is pressed, it may be delete. The transfer equation is:
$$
dp[n+1][max(c-1,0)]+=dp[n][c]
$$
If you press 0, the transfer equation is:
$$
dp[n+1][c+1]+=dp[n][c]
$$
In the same way as 1, add dp[n][c] to the above formula.
In the end, because 0 and 1 are fixed, it is divided by 2^len.