CF 1437 C. Chef Monocarp dp 1800

题意：有n道菜有自己的最佳烹饪时间（t1，t2，t3……tn），选n个出菜时间点（T1，T2，T3……Tn），使| ti - Ti |的总值最小。

思路：动态规划。状态表示：dp[i][j]的集合表示前 i 道菜在前 j 个时间点选择 i 个时间点出菜；属性是最小值。状态计算：dp[i][j] = min(dp[i - 1][j - 1] + abs(j - a[i]), dp[i][j - 1]);

代码

#include
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair PII;
const int N = 2e5 + 10, P = 1e9 + 7, mod = 998244353;
int a[N];
int dp[210][410];
void solve(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + 1 + n);
	memset(dp, 0x3f, sizeof dp);
	for(int i = 0; i <= 2 * n; i++) dp[0][i] = 0;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= 2 * n; j++)
			dp[i][j] = min(dp[i - 1][j - 1] + abs(j - a[i]), dp[i][j - 1]);
	cout << dp[n][2 * n] << endl;
}               
int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t;
	cin >>t;
	while(t--){
		solve();
	}
	return 0;
}