题解 P3035 【[USACO11DEC]伞头Umbrellas for Cows】

· · 题解

题意：

给定n个点，坐标为1~m之间的正整数且互不相同，现在要求用一段或多段线段将n个点覆盖，每种长度的线段都有一个价格（不满足单调性），求出最小价格

看完题目第一想法就应该是DP，贪心应该是不行的

其中a[i]表示第i个点的位置，cost[i]表示长度为i的线段的价格

但题目明确指出，长度增加价格未必会增加，也就是说有可能更长的线段的价格反而比长度为a[i]-a[j]+1的便宜

因为只要长度比a[i]-a[j]+1更长就能覆盖，所以我们只要在cost[a[i]-a[j]+1] ~ cost[m]选一个最小值即可，最小值怎么找？每次都O(n)找一遍？显然会超时，一个很简单最小后缀值提前预处理一遍就行了

详见代码：

#include<bits/stdc++.h>
#define maxn 200005
using namespace std;
int n,m,f[maxn],Ans,lst[maxn],a[maxn],v[maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-f;ch=getchar();}
    while (ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
int main(){
    n=read(),m=read();memset(f,63,sizeof f);f[0]=0;
    for (int i=1;i<=n;i++) a[i]=read();sort(a+1,a+n+1);
    for (int i=1;i<=m;i++) v[i]=read();v[0]=1<<30;lst[m+1]=1<<30;
    for (int i=m;i>=0;i--) lst[i]=min(v[i],lst[i+1]);
    for (int i=1;i<=n;i++)
        for (int j=i;j;j--) f[i]=min(f[i],f[j-1]+lst[a[i]-a[j]+1]);
    printf("%d",f[n]);
    return 0;
}