题解 P3049 【[USACO12MAR]园林绿化Landscaping】

· · 题解

网校的讲法+蒟蒻本兔自己的理解qwq

入门dp第三天看到这个题非常懵x

今天终于看懂了激动得来发篇题解！！！

把输入的初始数组和目标数组转化成如下格式：

a 2 3 4 5

a'1 1 2 2 2 3 3 3 3 4 4 4 4 4

b 3 1 5 2

b'1 1 1 2 3 3 3 3 3 4 4

这样思路就很清晰的，想必大家都能明白（除了我

#include<bits/stdc++.h>//3049
using namespace std;
int n,x,y,z,a[1010],b[1010],f[1010][1010],p,q;
int minx(int a,int b,int c)
{
    if(a<=b &&a<=c)return a;
    if(b<=a &&b<=c)return b;
    if(c<=a &&c<=b)return c;
}

int main()
{
    int la=1,lb=1;
    cin>>n>>x>>y>>z;
    for(int i=1;i<=n;i++){
    cin>>p>>q;
    for(int j=1;j<=p;j++)a[la++]=i;
    for(int k=1;k<=q;k++)b[lb++]=i;
    }
    f[0][0]=0;
    //极限情况作为边界 
    for(int i=1;i<=la;i++)f[i][0]=i*y;//目标为空数组 
    for(int i=1;i<=lb;i++)f[0][i]=i*x;//原数组为空 

    for(int i=1;i<=la;i++){
      for(int j=1;j<=lb;j++){
        f[i][j]=minx(f[i-1][j]+y,f[i][j-1]+x,f[i-1][j-1]+z*abs(a[i]-b[j]));
      }
      }
    cout<<f[la][lb]<<endl;
    return 0;
}