HBC24146简写单词,字符串[USACO 2011 Dec S]Umbrellas for Cows题解

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

Today is a rainy day!Farmer John's N (1

Today is a rainy day! Farmer John's N (1 <= N <= 5,000) cows, numbered 1..N, are not particularly fond of getting wet. The cows are standing in roofless stalls arranged on a number line. The stalls span X-coordinates from 1 to M (1 <= M <= 100,000). Cow i stands at a stall on coordinate X_i (1 <= X_i <= M) X i ​ (1<=X i ​ <=M). No two cows share stalls. In order to protect the cows from the rain, Farmer John wants to buy them umbrellas. An umbrella that spans coordinates X_i to X_j (X_i <= X_j) X i ​ toX j ​ (X i ​ <=X j ​ ) has a width of X_j - X_i + 1. X j ​ −X i ​ +1. It costs C_W (1 <= C_W <= 1,000,000) C W ​ (1<=C W ​ <=1,000,000) to buy an umbrella of width W. Larger umbrellas do not necessarily cost more than smaller umbrellas. Help Farmer John find the minimum cost it takes to purchase a set of umbrellas that will protect every cow from the rain. Note that the set of umbrellas in an optimal solution might overlap to some extent.

标签： HBC24146简写单词 字符串[USACO 2011 Dec S]Umbrellas for Cows题解