Brief solutions for problem D and E.
Category: DP
BZOJ2442: Mowing the Lawn[USACO2011 Open]
Problem Description: Mowing the Lawn [Neal Wu, 2008] After winning the annual town competition for best lawn a year ago,Farmer John has grown lazy; he has not mowed the lawn since thenand thus his lawn has become unruly. However, the competition isonce again coming soon, and FJ would like to get his lawn intotiptop shape […]
AtCoder Regular 099E: Independence
Problem Description: https://arc099.contest.atcoder.jp/tasks/arc099_c This problem is one that requires thoughts on complement graph. The official editorial has done a pretty good job in explanation. Step: Convert into complement graph -> Find characteristic of this graph -> Bipartite graph -> Convert back -> Find minimum roads -> DP #include <iostream> #include <cstring> #include <string> #include <vector> #include […]
BZOJ1556: The Secret of the Grave
Problem Description: You start at a point (sx,sy). There are T gravestones at on the map. You can destroy(diss joy?) a gravestone by touch the four sides that are adjacent to it. After destroying a gravestone, the gravestone turns into a wall, which you cannot pass through. As a Übermensch, you can move in one […]
P2519: problem a [HAOI2011]
Problem Description: N students are in classroom, the ith student says there are students that have scores higher than me and students that have scores lower than me(There might exist same scores). Please give out the minimum possible number of students that are lying. Input Format: First line with one integer N ≤ 100000 Next […]
P2515: Software Installation [HAOI2010]
Problem Description: You have computer with M amount of storage. There are N softwares you are going to install on the computer. The ith computer takes amount of storage and has a value of . There are also dependencies between softwares. Specifically, the ith software can be installed only if is installed. Every software can be only installed once, […]