题目
https://codeforces.com/contest/1437/problem/C
思路
dp，先对$a_i$升序排序，设$dp(i,j)$，$i$为前$a_i$的情况，$j$为选择减去的数字。初始化$dp(i,0)$为$\infty$（因为不能取0），状态转移方程$dp(i,j)\leftarrow\max(dp(i,j-1),dp(i-1,j-1)+abs(a_i-j))$。
注意$j$可能的取值，考虑$n,t$最大为200，则$j$最大取值为$200+199=399$，这里取405。
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
struct _IO { _IO() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); } }_io;
typedef long long ll; typedef long double ld; typedef pair<ll, ll> pll;
ll n, a[205], dp[205][405];
int main()
{
ll T;
cin >> T;
while (T--)
{
cin >> n;
for (ll i = 0; i < n; ++i) cin >> a[i];
sort(a, a + n);
for (ll i = 0; i < n; ++i) dp[i][0] = 1e12;
for (ll i = 1; i < 405; ++i)
dp[0][i] = min(dp[0][i - 1], abs(a[0] - i));
for (ll i = 1; i < n; ++i)
{
for (ll j = 1; j < 405; ++j)
{
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j - 1] + abs(a[i] - j));
}
}
cout << dp[n - 1][405 - 1] << endl;
}
return 0;
}
|