Can you come up with a solution to make your friends less expensive?

RioTian 2020-11-08 00:23:08
come solution make friends expensive

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 :

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 ?


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

\[n≤2⋅10^5 \]

1 0 1 1 0 1 1 1

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])
# 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;
cin >> ans;
while (n--) {
cin >> x;
if (x)
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 .


  1. [front end -- JavaScript] knowledge point (IV) -- memory leakage in the project (I)
  2. This mechanism in JS
  3. Vue 3.0 source code learning 1 --- rendering process of components
  4. Learning the realization of canvas and simple drawing
  5. gin里获取http请求过来的参数
  6. vue3的新特性
  7. Get the parameters from HTTP request in gin
  8. New features of vue3
  9. vue-cli 引入腾讯地图(最新 api,rocketmq原理面试
  10. Vue 学习笔记(3,免费Java高级工程师学习资源
  11. Vue 学习笔记(2,Java编程视频教程
  12. Vue cli introduces Tencent maps (the latest API, rocketmq)
  13. Vue learning notes (3, free Java senior engineer learning resources)
  14. Vue learning notes (2, Java programming video tutorial)
  15. 【Vue】—props属性
  16. 【Vue】—创建组件
  17. [Vue] - props attribute
  18. [Vue] - create component
  19. 浅谈vue响应式原理及发布订阅模式和观察者模式
  20. On Vue responsive principle, publish subscribe mode and observer mode
  21. 浅谈vue响应式原理及发布订阅模式和观察者模式
  22. On Vue responsive principle, publish subscribe mode and observer mode
  23. Xiaobai can understand it. It only takes 4 steps to solve the problem of Vue keep alive cache component
  24. Publish, subscribe and observer of design patterns
  25. Summary of common content added in ES6 + (II)
  26. No.8 Vue element admin learning (III) vuex learning and login method analysis
  27. Write a mini webpack project construction tool
  28. Shopping cart (front-end static page preparation)
  29. Introduction to the fluent platform
  30. Webpack5 cache
  31. The difference between drop-down box select option and datalist
  32. CSS review (III)
  33. Node.js学习笔记【七】
  34. Node.js learning notes [VII]
  35. Vue Router根据后台数据加载不同的组件(思考-&gt;实现-&gt;不止于实现)
  36. Vue router loads different components according to background data (thinking - & gt; Implementation - & gt; (more than implementation)
  37. 【JQuery框架,Java编程教程视频下载
  38. [jQuery framework, Java programming tutorial video download
  39. Vue Router根据后台数据加载不同的组件(思考-&gt;实现-&gt;不止于实现)
  40. Vue router loads different components according to background data (thinking - & gt; Implementation - & gt; (more than implementation)
  41. 【Vue,阿里P8大佬亲自教你
  42. 【Vue基础知识总结 5,字节跳动算法工程师面试经验
  43. [Vue, Ali P8 teaches you personally
  44. [Vue basic knowledge summary 5. Interview experience of byte beating Algorithm Engineer
  45. 【问题记录】- 谷歌浏览器 Html生成PDF
  46. [problem record] - PDF generated by Google browser HTML
  47. 【问题记录】- 谷歌浏览器 Html生成PDF
  48. [problem record] - PDF generated by Google browser HTML
  49. 【JavaScript】查漏补缺 —数组中reduce()方法
  50. [JavaScript] leak checking and defect filling - reduce() method in array
  51. 【重识 HTML (3),350道Java面试真题分享
  52. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  53. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  54. [re recognize HTML (3) and share 350 real Java interview questions
  55. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  56. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  57. 【重识 HTML ,nginx面试题阿里
  58. 【重识 HTML (4),ELK原来这么简单
  59. [re recognize HTML, nginx interview questions]
  60. [re recognize HTML (4). Elk is so simple