题解 P2214 【[USACO14MAR]哞哞哞Mooo Moo】

· · 题解

我看不出这道题和标签上的RMQ有什么关系。。。 记忆化搜索完全可以水过去~~ 介绍一下我的做法。设i农场自身奶牛产生的音量为B[i],显然A[i-1]!=0时A[i]=B[i]+A[i-1]-1;A[i-1]=0时,A[i]=B[i],得到了 B[i]=A[i-1]?A[i]-A[i-1]+1 : A[i]。 再对B[i]进行搜索，算出最少奶牛头数

下面贴代码。轻松+愉快就做完了~

#include<bits/stdc++.h>
const int N=1e7+5,INF=~0U>>2;
int n,m,tot;
int f[N],A[1000],v[30];
using namespace std;
//记忆化搜索
int F(int x){
    if(x<0)return INF;
    if(x==0)return 0;
    if(x>0&&f[x]!=0)return f[x];
    int ans=INF;
    for(int i=1;i<=m;++i)ans=min(ans,1+F(x-v[i]));
    return f[x]=ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)scanf("%d",&v[i]),f[v[i]]=1;
    for(int i=1;i<=n;++i)scanf("%d",&A[i]);
    for(int i=1;i<=n;++i)tot+=F(A[i-1]?A[i]-A[i-1]+1:A[i]);
    if(tot>INF)printf("-1");//判断是否存在方案
    else printf("%d",tot);
}