求助

Mike_python小

昨天看到了个题目，题目为下，正好我对这方面也不是很熟，就想着做这个练练手，但！我不会做，有大佬知道这个怎么做吗

1. Farmer John 有 N（1≤N≤105）头奶牛，每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。她们沿水平方向排成一行，奶牛们占据的位置编号为 1…N。
   
2. 由于奶牛们都饿了，FJ 决定在 1…N 中的某些位置上种植草地。更赛牛和荷斯坦牛喜欢不同类型的草，所以如果 Farmer John 决定在某个位置种草，他必须选择种植更赛牛喜欢的草或荷斯坦牛喜欢的草——他不能在同一个位置同时种两种草。种植的每一片草地都可以喂饱数量不限的相应品种的奶牛。
   
3. 
   
4. 每头奶牛愿意移动至多 K（0≤K≤N−1）个位置以前往一个草地。求出喂饱所有奶牛所需种植的最小草地数量。此外，输出一种使用最小草地数量喂饱所有奶牛的种植方案。任何满足上述条件的方案均视为正确。
   
5. 
   
6. 输入格式（从终端 / 标准输入读入）：
   
7. 每个测试用例包含 T 个子测试用例，为一种奶牛的排列。输入的第一行包含 T（1≤T≤10）。以下是 T 个子测试用例。
   
8. 每个子测试用例的第一行包含 N 和 K。第二行包含一个长度为 N 的字符串，其中第 i 个字符表示第 i 头奶牛的品种（G 表示更赛牛，H 表示荷斯坦牛）。
   
9. 
   
10. 输出格式（输出至终端 / 标准输出）：
    
11. 对于 T 个子测试用例中的每一个，输出两行。第一行输出喂饱所有奶牛所需的最小草地数量。第二行输出一个长度为 N 的字符串，表示一种使用最小草地数量喂饱所有奶牛的种植方案。第 i 个字符表示第 i 个位置，若不种草则为 '.'，若种植喂饱更赛牛的草则为 'G'，若种植喂饱荷斯坦牛的草则为 'H'。任何合法的方案均可通过。
    
12. 输入样例：
    
13. 6
    
14. 5 0
    
15. GHHGG
    
16. 5 1
    
17. GHHGG
    
18. 5 2
    
19. GHHGG
    
20. 5 3
    
21. GHHGG
    
22. 5 4
    
23. GHHGG
    
24. 2 1
    
25. GH
    
26. 输出样例：
    
27. 5
    
28. GHHGG
    
29. 3
    
30. .GH.G
    
31. 2
    
32. ..GH.
    
33. 2
    
34. ...GH
    
35. 2
    
36. ...HG
    
37. 2
    
38. HG
    
39. 注意对于某些子测试用例，存在多种可通过的方案使用最小数量的草地。例如，在第四个子测试用例中，以下是另一个可以通过的答案：
    
40. 
    
41. .GH..
    
42. 这个方案在第二个位置种植一块喂饱更赛牛的草地以及在第三个位置种植一块喂饱荷斯坦牛的草地。这使用了最小数量的草地并确保了所有奶牛都在她们喜欢的草地的 3 个位置以内。
    
43. 
    
44. 测试点性质：
    
45. 测试点 2-4 满足 N≤10。
    
46. 测试点 5-8 满足 N≤40。
    
47. 测试点 9-12 满足 N≤105。

复制代码

张育玮

能吧题目链接发出来吗？

Mike_python小

张育玮 发表于 2022-12-18 11:49
能吧题目链接发出来吗？

题目总共就是这些，发链接我怕被

zhangjinxuan

巧了，这道题我当时也没打出来

zhangjinxuan

张育玮 发表于 2022-12-18 11:49
能吧题目链接发出来吗？

http://www.usaco.org/index.php?page=viewproblem&cpid=1240

zhangjinxuan

zhangjinxuan 发表于 2022-12-18 21:15
巧了，这道题我当时也没打出来

怕被什么？

EODVT

怎么筛出最小方案？

EODVT

EODVT