题目链接:https://codeforces.com/problemset/problem/1437/C
用时少的一定比用时大的先拿更优,所以按用时大小排个序,
然后按顺序 \(dp\),用时最多不会超过 \(2*n\)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 210;
int T, n;
int a[maxn], f[maxn][maxn*2];
struct P{
int t,id;
}p[maxn];
bool cmp(P x, P y){ return x.t < y.t; }
ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f; }
int main(){
T = read();
while(T--){
memset(f,0x3f,sizeof(f));
int ans = f[0][0];
n = read();
for(int i=1;i<=n;++i) p[i].t = read(), p[i].id = i;
sort(p+1,p+1+n,cmp);
for(int i=1;i<=n;++i) printf("%d ",p[i].t); printf("\n");
for(int j=1;j<=2*n;++j) f[1][j] = abs(p[1].t - j);
for(int i=1;i<=n;++i){
for(int j=1;j<2*n;++j){
f[i][j+1] = min(f[i][j+1],f[i-1][j] + (j+1-p[i].t));
}
}
for(int i=1;i<=n;++i){
printf("%d:",i);
for(int j=1;j<=2*n;++j){
printf("%d ",f[i][j]);
}printf("\n");
}
for(int j=p[n].t;j<=2*n;++j){
ans = min(ans, f[n][j]);
}
printf("%d\n",ans);
}
return 0;
}