题解 P2769 【猴子上树】

wasa855 · 2018-10-16 16:46:41 · 题解

首先此题一定要先对两个数组排序。
然后采用动态规划的思想，定义f[i][j]=前i只猴子上前j棵树的消耗的最小能量。
对于转移方程：如果j==1，即只有一棵树，那么f[i][j]必然等于f[i-1][j]+abs(a[i]-b[j])。
如果j==i，即i只猴子上i棵树，又因为每棵树上必有一致猴子，f[i][i]必然等于f[i-1][i-1]+abs(a[i]-b[i])。
对于其他情况，有两种情况，第一是第i只猴子独占第j棵树，第二是第i只猴子和其他猴子共享第j棵树，即从min(f[i-1][j],f[i-1][j-1])转移而来，最后加上abs(a[i]-b[j])就好了。
看到数据范围，最后结果可能会超过int(c++)的范围，所以要开long long(c++)，但经计算需要约190MB的空间，所以要开滚动数组。

最后，祝大家NOIP2018 RP++。

附上代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 4611686018427387903
ll mon[5005];
ll tree[5005];
ll f[2][5005];
int main()
{
    int n,m;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&mon[i]);
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&tree[i]);
    }
    sort(mon+1,mon+n+1);
    sort(tree+1,tree+m+1);
    f[1][1]=abs(mon[1]-tree[1]);
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(j==1)
            {
                f[i%2][1]=f[(i-1)%2][1]+abs(mon[i]-tree[j]);
                continue;
            }
            if(i==j)
            {
                f[i%2][j]=f[(i-1)%2][j-1]+abs(mon[i]-tree[j]);
                break;
            }
            f[i%2][j]=min(f[(i-1)%2][j],f[(i-1)%2][j-1])+abs(mon[i]-tree[j]);
        }
    }
    cout<<f[n%2][m]<<endl;
    return 0;
}