题目链接 http://codeforces.com/problemset/problem/988/F
令dp[i][j]为走到目标为i处，手里拿着第j把伞，同时注意，在某处可能存在不止一把伞
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <stack> #include <cstdlib> #include <iomanip> #include <cmath> #include <cassert> #include <ctime> #include <map> #include <set> using namespace std; #pragma comment(linker, "/stck:1024000000,1024000000") #define lowbit(x) (x&(-x)) #define max(x,y) (x>=y?x:y) #define min(x,y) (x<=y?x:y) #define MAX 100000000000000000 #define MOD 1000000007 #define pi acos(-1.0) #define ei exp(1) #define PI 3.1415926535897932384626433832 #define ios() ios::sync_with_stdio(true) #define INF 0x3f3f3f3f #define mem(a) (memset(a,0,sizeof(a))) typedef long long ll; int dp[2006][2006],a,n,m; int rain[2006],umbre[2006]; int val[2006],pos[2006]; int main() { scanf("%d%d%d",&a,&n,&m); memset(rain,0,sizeof(rain)); memset(umbre,0,sizeof(umbre)); a++; for(int i=0,x,y;i<n;i++) { scanf("%d%d",&x,&y); for(int j=x+1;j<=y;j++) rain[j]=1; } for(int i=1,x,y;i<=m;i++) { scanf("%d%d",&x,&y); x++; pos[i]=x; val[i]=y; if(!umbre[x] || (umbre[x] && y<val[umbre[x]])) umbre[x]=i; } memset(dp,INF,sizeof(dp)); dp[0][0]=0; for(int i=0;i<a;i++) { for(int j=0;j<=m;j++) { if(pos[j]>i) continue; if(j) dp[i+1][j]=min(dp[i+1][j],dp[i][j]+val[j]); if(!rain[i]) dp[i+1][0]=min(dp[i+1][0],dp[i][j]); if(umbre[i]) dp[i+1][umbre[i]]=min(dp[i+1][umbre[i]],dp[i][j]+val[umbre[i]]);//同一个点可能存在多个雨伞 } } int ans=INF; for(int i=0;i<=m;i++) ans=min(ans,dp[a][i]); printf("%d ",ans>=INF?-1:ans); return 0; }