2018-04-20 21:21:03

网校的讲法+蒟蒻本兔自己的理解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
    
     //3049using 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<
     
      <