stay TechFlow The student's official account was found interesting CF Algorithm problem , Now let's use the idea of a senior student to learn
Topic link ：https://codeforces.com/contest/1418/problem/C
The question
The meaning of this question is also very interesting , The background is also a game . It's said that one day you play games at home with your girlfriends , This game has n individual boss. these boss The difficulty is different , There are some boss Simple , There are some boss difficult . Your technique is better than that of Kiyoshi , You two take turns fighting boss.
The rules of the game are to play at least once 1 individual boss, Two at most boss. Because you are better , You can beat all the boss. But your girlfriends compare dishes , It can only be played simply boss, If you come across hard Mode boss It's krypton gold . Foundation friend's money is also money , You want to be in Try to minimize krypton gold Under the premise of the game clearance . Now we know all of boss The difficulty of the situation and friends start the game first , Under the best strategy , How many times does krypton need at least ？
Examples
First give a number t, Represents the number of test data sets . For each set of data , Given a number n, Express boss The number of . And then give n individual 0 perhaps 1 The integer of ,0 Express boss It's a simple model ,1 It means difficult mode . Request to return a number , That's the minimum number of krypton gold . among
input:
8
1 0 1 1 0 1 1 1
output:
2
Sample explanation
You kill first 1 and 2 Two boss, Krypton gold once .
“ I ” kill 3 and 4 Number boss
Jiyou killed 5 Number boss
“ I ” kill 6 and 7 Number boss
Jiyou kills 8 Number boss, Krypton gold once , Krypton gold twice in all .
Answer key
The first thing we think about is greed , For example, we can think of a greedy strategy , It's just that every time they kill monsters, they kill them first 1 individual , And the second one is 0 still 1, If it is 0 They killed together , Otherwise, it will not be killed and left to “ I ”.
We can judge whether the greedy strategy is feasible by using the equivalent judgment method introduced before , For this question , The essence of greed is to make krypton gold the least . So the second weirdo of being a foundation friend is 0 When , Killing or not has no effect on the current number of krypton gold . however It will have an impact on the later situation Of , And there may be different results .
For example, we can find an example 10011, You can't kill the second monster , Directly affect the later results . If the guy kills , So regardless of “ I ” How to choose , You have to have krypton gold at least once again . If you don't kill , that “ I ” Kill the second monster , Jiyou kills the third monster , The last two boss All to “ I ”, Well, the whole situation of geek only needs krypton once . So greedy algorithms don't work .
Dynamic programming
If you're familiar with dynamic programming , So it's almost a classic Dynamic programming problem . For every monster , It has two states , They were killed by their friends or by “ I ” kill . We use it 0 and 1 To represent separately ,0 It means that he was killed by a friend ,1 Said by “ I ” kill . Altogether n Strange , So we can use a n * 2 To record the status of all monsters .
For the first i In a strange way , If it is “ I ” Killed , Then it can be killed by a friend i-1 Or is it i-2 A strange state has been transferred to . For example, if you kill from a friend i-1 Transfer to get , explain “ I ” kill i, Otherwise, explain “ I ” Not only killed i, And killed i-1. Empathy i It's the same with being killed by a friend , So this state transition equation is very obvious .
# Senior students Python solution , The notes are full of
import sys
t = int(input())
for _ in range(t):
n = int(input())
arr = list(map(int, input().split(' ')))
dp = [[sys.maxsize, sys.maxsize] for _ in range(n+2)]
dp[0][1] = 0
for i in range(1, n+1):
if i > 1:
# If i > 1, So it means you can kill two
# 0 It's about the killing of monsters by geeks , Friends can kill 1 From the i-1 Transfer to get , You can also kill 2 From the i-2 Transfer to get
# You need to add the number of krypton gold
dp[i][0] = min(dp[i-1][1] + arr[i-1], dp[i-2][1] + arr[i-2] + arr[i-1])
# I don't need krypton gold , Direct assignment
dp[i][1] = min(dp[i-1][0], dp[i-2][0])
else:
# i=1, Then only one can be killed
dp[i][0] = dp[i-1][1] + arr[i-1]
dp[i][1] = dp[i-1][0]
print(min(dp[n][0], dp[n][1]))
// Konnyaku C++ solution
// Author : RioTian
// Time : 20/11/07
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int main() {
// freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int x, ans = 0, sum = 0;
n--;
cin >> ans;
while (n--) {
cin >> x;
if (x)
sum++;
else
ans += sum / 3, sum = 0;
}
cout << ans + sum / 3 << endl;
}
}
Last , This problem is very basic , It can be said that it is the basic problem of dynamic programming . If you're not familiar with the concept of dynamic programming , It's highly recommended that you do it yourself , Make a deep impression .