[CF1437C] Chef Monocarp

Description

有 n 道菜品被放入了一个烤炉中，每到菜品都有一个最佳取出的时间 (t_i)。现在按照一定顺序把菜品从烤炉中取出，每到菜品都有可能因为不在最佳时间被取出而造成不美味，定义这个不美味度为 (|T-t_i|)，其中 T 是取出的时刻。求把所有菜品都取出来的最小不美味度。(n le 200)

Solution

考虑到取出所有菜品的顺序一定与他们完成的时间先后顺序相同，设 (f[i][j]) 表示到了时刻 (i) 取出了前 (j) 个菜品，那么很显然有转移 (f[i][j]=min (f[i-1][j],f[i-1][j-1]+|i-t[j]|))，可以压掉一维倒序转移。

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 1005;

int n,t[N],f[N],tmax;

signed main()
{
    int _;
    cin>>_;
    while(_--)
    {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>t[i];
        sort(t+1,t+n+1);
        memset(f,0x3f,sizeof f);
        f[0]=0;
        for(int i=1;i<N;i++)
        {
            for(int j=n;j>=1;j--)
            {
                f[j]=min(f[j],f[j-1]+abs(i-t[j]));
            }
        }
        cout<<f[n]<<endl;
    }
}