cf C. Chef Monocarp
这道dp题，我卡住了。
主要是我陷入了一个思维误区。
没有好好分析题目，获得所有的条件信息。
我是这样想的。对于每一个时间i
我有两种选择
1.拿后面没拿的
2.拿前面没拿的
但是，这种分析十分的困难，我还要判断是否此刻有料理为最佳出锅时间。
真的是十分麻烦。
我漏了一个重要信息：
其实，我们完全可以从头往后拿！！！！
对于任意时刻，你拿前面或者你拿后面收益其实是相等的！！！！！！
也就是，我们可以这样总结状态dp[i][j]在第i分钟，拿了前j个料理的最小不愉快度
那么，既然那前面和拿后面都一样的话，到底什么取决最小不愉快度呢？
拿不拿的问题，即在一些时间我可能是不拿的。
算上不拿的时间，其实我最多会耗到2*n的时刻。
dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]+abs(i-t[i]))
算到dp[2n][n]
真的是巧妙，要好好观察总结信息
#include<iostream>
#include<algorithm>
using namespace std;
const int inf = 1e9;
int dp[410][210];
int a[210];
int main() {
ios::sync_with_stdio(0);
int T;cin >> T;
while (T--) {
int n;cin >> n;
for (int i = 1;i <= n;++i) cin >> a[i];
sort(a + 1, a + 1 + n);
for (int j = 1;j <= n;++j)dp[0][j] = inf;
for (int i = 1;i <= (n << 1);++i)
for (int j = 1;j <= n;++j)
dp[i][j] = min(dp[i - 1][j - 1] + abs(i - a[j]), dp[i - 1][j]);
cout << dp[n << 1][n] << endl;
}
}
查看7道真题和解析
