题解 P2893 【[USACO08FEB]修路Making the Grade】

SUNCHAOYI · 2019-08-03 13:29:24 · 题解

首先设f[i][j]表示长为i，高为j的不下降/不上升的序列长度 那么状态转移f[i][j] = q[i - 1][j] + abs(a[i] - c[j]); q数组是记录最优解的，同时q数组也要更新

if(j != 1) q[i][j] = min(f[i][j],q[i][j - 1]);
else q[i][j] = f[i][j];

先把数据输入后排序，然后进行dp后再变为降序进行dp

两次的答案取最小值即可

代码：

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAX = 2010;
int a[MAX],b[MAX],c[MAX],f[MAX][MAX],k = -1,m = 0,n,q[MAX][MAX],ans = 0x3f3f3f3f;
void ready();
void work();
int main()
{
    cin>>n;
    for(int i = 1;i <= n;i++)
    {
        cin>>a[i];
        b[i] = a[i];
    }
    sort(b + 1,b + n + 1);//排成上升序列
    for(int i = 1;i <= n;i++)//有无重复
        if (k != b[i]){c[++m] = b[i],k = b[i];}
    //上升下降各找一遍取min
    ready();work();ans = q[n][m];
    for(int i = 1;i <= m / 2;i++) swap(c[i],c[m - i + 1]);//交换后成下降序列
    ready();work();ans = min(ans,q[n][m]);
    cout<<ans<<endl;
    return 0;
}
void ready()//初始化
{
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++) f[i][j] = q[i][j] = 0;
}
void work()
{
    //q记录最小的，最优解；f用来转移
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            f[i][j] = q[i - 1][j] + abs(a[i] - c[j]);
            if(j != 1) q[i][j] = min(f[i][j],q[i][j - 1]);
            else q[i][j] = f[i][j];
        }
    }
}