CodeForces 988F Rain and Umbrellas

题目

◇题目传送门◆

题目大意

有一个人在数轴上的原点，他想到达$A$点，但路上有$N$区间在下雨，在下雨的区间内必须打伞，他却没有伞。但是路上有$M$把伞，每个伞有两个属性——$x,p$，$x$表示伞的位置，$p$表示伞的重量。每携带$1$单位重量的伞走$1$个单位长度需要消耗$1$单位体力，求从$0$到$A$消耗的最少体力。

思路

一道~~裸且简单的~~DP题。

我们设$w[i]$为位于$i$点的伞的重量值,若值为$\infty$，则该处无伞。$rain[i]$表示$i$段是否下雨。设$F[i]$为由$0$~$i$的最少体力消耗。

则得出状态转移方程：

$$F[i]=\{^{F[i-1](rain[i]=false,1\le i\le A)}_{min\{F[j]+(i-j)\times w[j]\}(w[j]\ne \infty,0\le j<i,1\le i\le A)}$$

答案即为$F[A]$。

实现细节

注意：一个点可能有多把伞，我们只需取重量最小的那一个。

正解代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int Maxn=2000;
const long long INF=1e18;
int A,N,M;long long dp[Maxn+5],W[Maxn+5];
bool Is_rain[Maxn+5];int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endiffill(dp,dp+Maxn+1,INF);fill(W,W+Maxn+1,INF);dp[0]=0;scanf("%d %d %d",&A,&N,&M);for(int i=1;i<=N;i++) {int l,r;scanf("%d %d",&l,&r);for(int j=l;j<r;j++)Is_rain[j]=true;}for(int i=1;i<=M;i++) {int x;long long w;scanf("%d %lld",&x,&w);W[x]=min(W[x],w);}for(int i=1;i<=A;i++)if(!Is_rain[i-1]) {dp[i]=dp[i-1];} else {for(int j=i-1;j>=0;j--)if(W[j]!=INF)dp[i]=min(dp[i],dp[j]+(i-j)*W[j]);}printf("%lld\n",dp[A]==INF?-1:dp[A]);return 0;
}