题目链接:https://codeforces.ml/problemset/problem/1437/C
题意:给定n道菜 每个时间只能拿出一道菜, 每道菜的不愉快值= 拿出的时间和a[i]的差值
求总的不愉快值最小值为多少
思路:发现直接匹配最小的差值不行 排序后直接匹配找最小的差值也不行
那么只能考虑通过dp来确定当前的这个位置要不要放这个数, 因为要转移 所以肯定是先放小的数才放大的数这样最优来转移
dp[i][j] 代表已经拿出i道菜后 时间为j的最小值 所以在时间为j时 每道菜就可以拿出或者不拿出
dp[i][j]=min(dp[i-1][j-1]+abs(a[i]-j),dp[i][j-1]) 拿的话就是前一道菜的前一秒, 因为这一秒的话不能让前一道菜拿了, 或者上一秒的时候拿了这一道菜
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define pb push_back 4 #define ll long long 5 const int maxn=1e5+10; 6 const int mod=1e9+7; 7 int a[210]; 8 int dp[222][222*2]; 9 10 11 12 int main() 13 { 14 ios::sync_with_stdio(0); 15 cin.tie(0); 16 int q; 17 cin>>q; 18 while(q--) 19 { 20 int n; 21 cin>>n; 22 for(int i=1;i<=n;i++) 23 { 24 cin>>a[i]; 25 } 26 sort(a+1,a+1+n); 27 for(int i=1;i<=n;i++) 28 { 29 dp[i][0]=1e9; 30 for(int j=1;j<=n*2+2;j++) 31 { 32 dp[i][j]=min(dp[i-1][j-1]+abs(a[i]-j),dp[i][j-1]); 33 } 34 } 35 cout<<dp[n][n*2+2]<<'\n'; 36 37 } 38 39 40 }View Code