原题链接
题意：
将n个菜放入烤箱，每个菜的最佳取出时间为t[i]，每个时刻只能够取出一道菜。在时刻T取出第i个菜的不愉快值为abs(t[i]-T)。求最小的不愉快值。
思路：
首先，将t按照从小到大排序，因为取出时间早的越早拿是最优的。（好像并不准确.jpg）;
考虑动态规划，dp[i] [j] 表示到时刻i取出了j个菜的最小不愉快值。划分依据为是否在时刻i取出第j个菜：
如果取出第j个菜的话，那么上一个状态就是到时刻i-1取出了j-1个菜，本次对答案的贡献是abs(i-t[j])；
如果不取出第j个菜的话，上一个状态就是到时刻i-1取出了j个菜；
两者取最小值即可。
再来考虑dp数组的初始化，dp[i][0]=0，还是比较好理解的。
最后有个小优化的地方，因为题目里说了t[i]<=n，所以考虑最优解的话，花费的时间最多是2n。优化40ms左右。
代码：
#include<bits/stdc++.h> using namespace std; int dp[1110][1010]; ///dp[i][j]表示截止到时刻i取出了j个菜 int t[1010]; int main(){ int T;cin>>T; while(T--){ int n;cin>>n; for(int i=1;i<=n;i++) cin>>t[i]; sort(t+1,t+1+n);///时间小的先拿较优 memset(dp,0x3f,sizeof dp); for(int i=0;i<=1000;i++) dp[i][0]=0; for(int i=1;i<=1000;i++){ for(int j=1;j<=n;j++){ dp[i][j]=min(dp[i-1][j-1]+abs(t[j]-i),dp[i-1][j]); } } int res=1e9; for(int i=1;i<=1000;i++) res=min(res,dp[i][n]); cout<<res<<endl; } return 0; }
