题目链接：http://codeforces.com/contest/988/problem/F
题目大意：
有三个整数a,n,m，a是终点坐标，给出n个范围（l,r）表示这块区域下雨，m把伞(p,w)在点p有重量为w的伞。
小明可以携带任意数量的伞，经过下雨处时必须要撑伞，小明每走一个单位长度消耗的体力与他所携带伞的重量相同，
求小明从0~a所需消耗的最少体力，若无解则输出-1。
解题思路：
第一种解法：
设dp[i]表示到达i点所需花费的最少体力，rain[i]表示第i段是否下雨（注意是段不是点）,ub[j]表示j点放置的伞的重量。
则当rain[i-1]=false时，dp[i]=dp[i]-1
rain[i-1]=true是，dp[i]=min{dp[j]+(i-j)*ub[j]}，（ub[j]!=1e18且j<=i-1）
复杂度O（n^2）
第二种解法：
设dp数组，
dp[i][0]表示到达第i段不拿伞最小花费
dp[i][1]表示到达第i段拿伞最小化费
dp[i][2]表示到达第i段拿最小重量的伞的最小化费
然后不想说了，各种递推就是了。。。
复杂度O（n）
代码：
解法一：
#include<bits/stdc++.h>
#define lc(a) (a<<1)
#define rc(a) (a<<1|1)
#define MID(a,b) ((a+b)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define clr(arr,val) memset(arr,val,sizeof(arr))
#define _for(i,start,end) for(int i=start;i<=end;i++)
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long LL;
const int N=2e3+;
const int INF=0x3f3f3f3f;
const double eps=1e-; LL dp[N],ub[N];
bool rain[N]; int main(){
FAST_IO;
int a,n,m;
cin>>a>>n>>m;
for(int i=;i<N;i++){
dp[i]=ub[i]=1e18;
}
for(int i=;i<=n;i++){
int l,r;
cin>>l>>r;
if(l>r) swap(l,r);
for(int j=l;j<=r-;j++){
rain[j]=true;
}
}
for(int i=;i<=m;i++){
LL p,w;
cin>>p>>w;
ub[p]=min(ub[p],w);
}
dp[]=;
for(int i=;i<=a;i++){
if(!rain[i-]){
dp[i]=dp[i-];
}
else{
for(int j=i-;j>=;j--){
if(ub[j]!=1e18)
dp[i]=min(dp[i],dp[j]+(i-j)*ub[j]);
}
}
}
if(dp[a]==1e18)
cout<<-<<endl;
else
cout<<dp[a]<<endl;
return ;
}
解法二：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<string.h>
#include<cctype>
#include<math.h>
#include<stdlib.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
#define lc(a) (a<<1)
#define rc(a) (a<<1|1)
#define MID(a,b) ((a+b)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define clr(arr,val) memset(arr,val,sizeof(arr))
#define _for(i,start,end) for(int i=start;i<=end;i++)
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long LL;
const int N=2e3+;
const int INF=0x3f3f3f3f;
const double eps=1e-; bool rain[N],flag[N];
LL dp[N][],ub[N];
//dp[i][0]表示到达第i段不拿伞最小花费
//dp[i][1]表示到达第i段拿伞最小化费
//dp[i][2]表示到达第i段拿最小重量的伞的最小化费 int main(){
FAST_IO;
int a,n,m;
cin>>a>>n>>m;
for(int i=;i<N;i++){
ub[i]=dp[i][]=dp[i][]=dp[i][]=1e18;
}
for(int i=;i<=n;i++){
int l,r;
if(l>r)
swap(l,r);
cin>>l>>r;
for(int j=l;j<=r-;j++){
rain[j]=true;
}
}
for(int i=;i<=m;i++){
LL p,w;
cin>>p>>w;
ub[p]=min(ub[p],w);
} if(!rain[])
dp[][]=;
dp[][]=dp[][]=ub[];
LL mmin=ub[],now=ub[];
for(int i=;i<=a-;i++){
if(ub[i]){
mmin=min(ub[i],mmin);
now=min(ub[i],now);
}
LL t=min(dp[i-][]+now,dp[i-][]+mmin);
dp[i][]=t;
if(t==dp[i-][]+mmin)
now=mmin;
dp[i][]=dp[i-][]+mmin; //下雨
if(rain[i]){
//有伞
if(ub[i]){
dp[i][]=min(dp[i-][]+ub[i],dp[i][]);
if(dp[i][]==dp[i-][]+ub[i])
now=ub[i];
if(mmin==ub[i]){
dp[i][]=min(dp[i-][]+mmin,dp[i][]);
}
}
}
//不下雨
else{
dp[i][]=min(dp[i-][],dp[i-][]);
//有伞
if(ub[i]){
dp[i][]=min(dp[i-][]+ub[i],dp[i][]);
if(dp[i][]==dp[i-][]+ub[i])
now=ub[i];
if(mmin==ub[i]){
dp[i][]=min(dp[i-][]+mmin,dp[i][]);
}
}
}
}
LL ans=min(dp[a-][],dp[a-][]);
if(ans!=1e18)
cout<<ans<<endl;
else
cout<<-<<endl;
return ;
}