CodeForces 988 F Rain and Umbrellas
题意：某同学从x=0的点走到x=a的点，路上有几段路程是下雨的， 如果他需要经过这几段下雨的路程， 需要手上有伞， 每一把伞有一个重量， 求走到重点重量×路程的最小花费。
题解：暴力，如果某段路程需要带伞，就直接去找前面有伞的地点，如果不需要伞就直接往后走就好了。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1e5; 4 const int INF = 0x3f3f3f3f; 5 int rain[N]; 6 int w[N]; 7 int dp[N]; 8 int main(){ 9 int a, n, m, l, r; 10 scanf("%d%d%d", &a, &n, &m); 11 for(int i = 1; i <= n; i++){ 12 scanf("%d%d", &l, &r); 13 for(int j = l; j <= r; j++) 14 rain[j] = i; 15 } 16 memset(dp, INF, sizeof(dp)); 17 memset(w, INF, sizeof(w)); 18 for(int i = 1; i <= m; i++){ 19 scanf("%d%d", &l, &r); 20 w[l] = min(w[l], r); 21 } 22 dp[0] = 0; 23 for(int i = 0; i < a; i++){ 24 if(rain[i] == rain[i+1] && rain[i]){ 25 for(int j = 0; j <= i; j++) 26 if(w[j]!=INF) dp[i+1] = min(dp[i+1], dp[j]+(i+1-j)*w[j]); 27 } 28 else dp[i+1] = dp[i]; 29 } 30 printf("%d ",dp[a]>=INF ? -1 : dp[a]); 31 32 }